?
题意：1元，2元，5元的硬币分别有num[1],num[2],num[3]个。问用这些硬币不能组合成的最小钱数。
继续母函数。
有两个注意的地方：
对c2[]初始化的同时也要对c1[]初始化。
最后枚举到sum+1，因为存在[1,sum]都可以凑成的可能，这时输出sum+1。
#include #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; int c1[8010],c2[8010]; int add[4] = {0,1,2,5}; int num[4]; int main() { while(~scanf(%d %d %d,&num[1],&num[2],&num[3])) { if(num[1] == 0 && num[2] == 0 && num[3] == 0) break; int sum = num[1] + num[2]*2 + num[3]*5; //可以到达的最高钱数 memset(c2,0,sizeof(c2)); memset(c1,0,sizeof(c1)); for(int i = 0; i <= num[1]; i++) { c1[i] = 1; } for(int i = 2; i <= 3; i++) { for(int j = 0; j <= sum; j++) { for(int k = 0; k+j <= sum && k <= add[i]*num[i]; k += add[i]) { c2[k+j] += c1[j]; } } for(int j = 0; j <= sum; j++) { c1[j] = c2[j]; c2[j] = 0; } } for(int i = 1; i <= sum+1; i++) //注意枚举到sum+1,因为若[1,sum]都可以凑成的话，应该输出sum+1. { if(c1[i] == 0) { printf(%d ,i); break; } } } return 0; }