usaco 2.3.4 Money Systems

1、本题是个完全背包问题，关于这个问题其实dd大神的背包九讲里面已经阐述得很清楚了。

2、用数组f[i]记录每一轮用货币组成总值为i的种类数。初始f[0]=1;

3、注意题目中的种类数在c中int型是存不下的，最后一组数据很大。用unsigned long long即可。

4、以下是代码：

#include<stdio.h>

#include<string.h>

int main(){

unsigned long long f[10001];

int v,n,tmp;

freopen("money.in","r",stdin);

freopen("money.out","w",stdout);

scanf("%d%d",&v,&n);

memset(f,0,sizeof(unsigned long long)*10001);

f[0]=1;

int j;

for(int i=1;i<=v;i++){

scanf("%d",&tmp);

for(j=tmp;j<=n;j++){

f[j]+=f[j-tmp];

}

}

printf("%lld\n",f[n]);

return 0;

}