【题目大意】
有n种硬币，面值分别为$a_1,a_2,…,a_n$，数量分别为$c_1,c_2,…,c_n$，现要求用这些硬币表示出[1,m]的金额，求能表示出的金额种数。
【思路分析】
假设$f[i]$表示能否表示出金额$i$，那么如果这个金额可以被表示出来，那么必然同时满足以下几个条件：
1.$f[i]=0$（这里只讨论之前没有没表示出来过的金额，如果被表示过了就跳过）
2.$f[i-a[j]]=1$，即之前某个被表示出来过的金额加上一种面值的硬币恰好等于当前的这个金额，那么就一定能被表示出来
3.$used[f[i]-a[j]]<c[j]$，即现在要加上的这种面值的硬币已经使用的数量小于其总数量，否则就不能用了
我们可以用循环将每种面值的硬币分开讨论，最后统计答案时将所有可以表示出来的金额累加即可。
【代码实现】
1 #include<cstdio> 2 #include<cstring> 3 #define gc getchar() 4 #define go(i,a,b) for(register int i=a;i<=b;i++) 5 using namespace std; 6 const int N=102; 7 const int M=1e5+2; 8 int n,m; 9 int fr(){ 10 int w=0,q=1; 11 char ch=gc; 12 while(ch<‘0‘||ch>‘9‘){ 13 if(ch==‘-‘) q=-1; 14 ch=gc; 15 } 16 while(ch>=‘0‘&&ch<=‘9‘) 17 w=(w<<1)+(w<<3)+ch-‘0‘,ch=gc; 18 return w*q; 19 } 20 int a[N],used[M],c[N]; 21 bool f[M]; 22 int main(){ 23 n=fr();m=fr(); 24 while(n&&m){ 25 memset(f,0,sizeof(f)); 26 go(i,1,n) a[i]=fr(); 27 go(i,1,n) c[i]=fr(); 28 f[0]=1; 29 go(i,1,n){ 30 memset(used,0,sizeof(used)); 31 //used[i]数组记录当前这种金额的时候用了多少个 32 go(j,a[i],m) 33 if(!f[j]&&f[j-a[i]]&&used[j-a[i]]<c[i]) 34 f[j]=1,used[j]=used[j-a[i]]+1; 35 } 36 int ans=0; 37 go(i,1,m) ans+=f[i]; 38 printf("%d\n",ans); 39 n=fr();m=fr(); 40 } 41 return 0; 42 }
原文：https://www.cnblogs.com/THWZF/p/10902704.html
