题目大意：某人有各种面值为ai的硬币ci个，问他能凑够1到m价格中的几个?
Input
The input contains several test cases. The first line of each test case contains two integers n(1<=n<=100),m(m<=100000).The second line contains 2n integers, denoting A1,A2,A3...An,C1,C2,C3...Cn (1<=Ai<=100000,1<=Ci<=1000). The last test case is followed by two zeros.
Output
For each test case output the answer on a single line.
Sample Input
3 10 1 2 4 2 1 1 2 5 1 4 2 1 0 0
Sample Output
8 4
动态规划，
dp[i][j]表示用前 i 个物品凑成 j 时物品还剩多少个，如果凑不出，就为-1
代码如下
1 /* 2 if(dp[i-1][j] >= 0) { 3 dp[i][j] = c[i]; 4 } 5 else { 6 if(j < v[i] || dp[i][j-v[i]] < 0) { 7 dp[i][j] = -1; 8 } 9 else { 10 dp[i][j] = dp[i][j-v[i]] - 1; 11 } 12 }*/ 13 #include <cstdio> 14 #include <cstring> 15 #include <cstdlib> 16 17 int dp[102][100002]; 18 int a[102], c[102]; 19 int main(int argc, char const *argv[]) 20 { 21 int n, m; 22 freopen("input.txt","r",stdin); 23 while(scanf("%d %d",&n,&m) != EOF && (n != 0 && m != 0)) { 24 for(int i = 1; i <= n; i++) { 25 scanf("%d",&a[i]); 26 } 27 for(int i = 1; i <= n; i++) { 28 scanf("%d",&c[i]); 29 } 30 memset(dp, 0, sizeof(dp)); 31 for(int i = 1; i <= n; i++) { 32 dp[i][0] = c[i]; 33 } 34 for(int i = 0; i <= m; i++) { 35 dp[0][i] = -1; 36 } 37 for(int i = 1; i <= n; i++) { 38 for(int j = 1; j <= m; j++) { 39 if(dp[i-1][j] >= 0) { 40 dp[i][j] = c[i]; 41 } 42 else { 43 if(j < a[i] || dp[i][j-a[i]] < 0) { 44 dp[i][j] = -1; 45 } 46 else { 47 dp[i][j] = dp[i][j-a[i]] - 1; 48 } 49 } 50 } 51 } 52 int ans = 0; 53 for(int i = 1; i <= m; i++) { 54 if(dp[n][i] >= 0) { 55 ans++; 56 } 57 } 58 printf("%d ",ans); 59 } 60 return 0; 61 }
关于转移方程，如果dp[i-1][j] >= 0 即用前i-1个物品就可以实现j，那么dp[i][j]就是第i个物品的个数
如果dp[i-1][j] == -1
如果j比第i个物品的价值小，那么凑不出
如果用前i个物品凑不出j-v[i]，那么也同样凑不出j
否则,dp[i][j]就为凑过j-1的物品数再减1
再将dp化为一维数组
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 5 int dp[100002]; 6 int a[102], c[102]; 7 int main(int argc, char const *argv[]) 8 { 9 int n, m; 10 //freopen("input.txt","r",stdin); 11 while(scanf("%d %d",&n,&m) != EOF && (n != 0 && m != 0)) { 12 for(int i = 1; i <= n; i++) { 13 scanf("%d",&a[i]); 14 } 15 for(int i = 1; i <= n; i++) { 16 scanf("%d",&c[i]); 17 } 18 memset(dp, 0, sizeof(dp)); 19 for(int i = 1; i <= m; i++) { 20 dp[i] = -1; 21 } 22 for(int i = 1; i <= n; i++) { 23 for(int j = 0; j <= m; j++) { 24 if(dp[j] >= 0) { 25 dp[j] = c[i]; 26 } 27 else if( j < a[i] || dp[j-a[i]] < 0) { 28 dp[j] = -1; 29 } 30 else { 31 dp[j] = dp[j-a[i]] - 1; 32 } 33 } 34 } 35 int ans = 0; 36 for(int i = 1; i <= m; i++) { 37 if(dp[i] >= 0) { 38 ans++; 39 } 40 } 41 printf("%d ",ans); 42 } 43 return 0; 44 }
貌似用母函数也可以求解这道题
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6 7 int a[102], c[102]; 8 int c1[100002] = {0}; 9 int c2[100002] = {0}; 10 int ans[100002] = {0}; 11 int p; 12 int n, m; 13 14 void multi(int cn1, int cn2) { 15 cn1 = min(cn1, m); 16 cn2 = min(cn2, m); 17 for(int i = 0; i <= cn1; i++) { 18 for(int j = 0; j <= cn2; j++) { 19 ans[i+j] = ans[i+j] + c1[i]*c2[j]; 20 } 21 } 22 p = cn1 + cn2; 23 } 24 25 int main(int argc, char const *argv[]) 26 { 27 28 freopen("input.txt","r",stdin); 29 while(scanf("%d %d",&n,&m) != EOF && (n != 0 && m != 0)) { 30 for(int i = 1; i <= n; i++) { 31 scanf("%d",&a[i]); 32 } 33 for(int i = 1; i <= n; i++) { 34 scanf("%d",&c[i]); 35 } 36 memset(ans, 0, sizeof(ans)); 37 for(int i = 0; i <= c[1]; i++) { 38 ans[i*a[1]] = 1; 39 } 40 p = a[1]*c[1]; 41 for(int i = 2; i <= n; i++) { 42 memset(c1, 0, sizeof(c1)); 43 memset(c2, 0, sizeof(c2)); 44 for(int j = 0; j <= p; j++) { 45 c1[j] = ans[j]; 46 } 47 for(int j = 0; j <= c[i]; j++) { 48 c2[j*a[i]] = 1; 49 } 50 memset(ans, 0, sizeof(ans)); 51 multi(p,a[i]*c[i]); 52 } 53 int anss = 0; 54 for(int i = 1; i <= m; i++) { 55 if(ans[i] > 0) { 56 anss++; 57 } 58 } 59 printf("%d ",anss); 60 } 61 return 0; 62 }
但是超时了