参考：

题意：给你n种面值的硬币，面值为a1...an，数量分别为c1...cn，求问，在这些硬币的组合下，能够多少种面值，该面值不超过m

 

思路：设d[i][j]——前i种硬币，凑成总值j时，第i种硬币所剩余的个数。

　　　默认d[i][j] = -1，代表无法凑成总值j

　　　转移方程为，若d[i-1][j]≥0，代表前i-1种已能够凑成j，那么就不必花费第i种硬币，所以d[i][j] = c[i]

　　　否则就看d[i][j-a[i]]的值，显然如果j < a[i]，那么d[i][j] = -1，否则d[i][j-a[i]] ≤ 0，代表此刻第i种硬币已使用完了，所以自然d[i][j] = -1;

　　　否则，d[i][j] = d[i][j-a[i]]-1;

　　　可以看到d[i][]的值只与d[i-1][]和d[i][]有关，所以我们可以采用一维数组的形式，从而能够节省内存空间。

 

 AC代码：

#include 
     
      #include 
      
       using namespace std;const int M = 100005;const int N = 105;int d[M];int n,a[N],c[N],m;void solve(){	memset(d, -1, sizeof(d));	d[0] = 0;		for(int i = 0; i < n; i++)	{		for(int j = 0; j <= m; j++)		{			if(d[j] >= 0) d[j] = c[i];			else if(j < a[i] || d[j-a[i]]<= 0)				d[j] = -1;			else d[j] = d[j-a[i]]-1;		}	}		int ans = 0;	for(int i = 1; i <= m; i++)		if(d[i]>=0) ans++;	printf("%d\n", ans);}int main(){	//freopen("in.txt", "r", stdin);	while(~scanf("%d %d", &n, &m) &&(n||m))	{		for(int i = 0; i < n; i++) scanf("%d", a+i);		for(int i = 0; i < n; i++) scanf("%d", c+i);		solve();	}	return 0;}