题意：给 17 种面值的钱币，分别为：1-4-9-。。。-17^2.问 x（x <= 300) 能有多少种不同的兑换方式。
思考：略~母函数简单模板题目。事实上还可以用完全背包来做。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std ; 7 const int maxn = 333 ; 8 int w[20] , c1[maxn] , c2[maxn] , k , N = 17 ; 9 10 inline void muhanshu()11 {12 for (int i = 0 ; i <= k ; ++ i) c1[i] = 1 , c2[i] = 0 ;13 for (int p = 2 ; p <= N ; ++ p) {14 for (int i = 0 ; i <= k ; ++ i) {15 for (int j = 0 ; j + i <= k ; j += w[p]) {16 c2[j+i] += c1[i] ;17 }18 }19 for (int i = 0 ; i <= k; ++ i) c1[i] = c2[i] , c2[i] = 0 ;20 }21 printf("%d\n",c1[k]) ;22 }23 24 int f[maxn] ;25 26 void beibao()27 {28 memset(f,0,sizeof(f)) ;29 f[0] = 1 ;30 for (int i = 1 ; i <= N ; ++ i) {31 for (int j = w[i] ; j <= k ; ++ j) {32 f[j] += f[j-w[i]] ;33 }34 }35 printf("%d\n",f[k]) ;36 }37 38 int main()39 {40 for (int i = 1 ; i <= 17 ; ++ i) w[i] = i*i ;41 while (scanf("%d",&k) == 1 && k) {42 //muhanshu() ;43 beibao() ;44 }45 return 0 ;46 }
题意：有 N 个砝码，一个天平，问 1 到 砝码之和范围内的数字哪个不能组成，注意，砝码放在同一边加，两边减，也就是说每个砝码可以取 -1个，0个，1个。
思考：需要思考么？？不过因为幂次可能有负数，所以同乘砝码和就ok了，注意输出格式。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std ; 7 const int maxn = 20010 ; 8 int c1[maxn] , c2[maxn] , sum , N , A[maxn] ; 9 10 int main()11 {12 // freopen("1.txt","r",stdin) ;13 while (scanf("%d",&N) == 1) {14 sum = 0 ;15 for (int i = 1 ; i <= N ; ++ i) scanf("%d",&A[i]) , sum += A[i] ;16 memset(c1,0,sizeof(c1)) ;17 memset(c2,0,sizeof(c2)) ;18 c1[0] = c1[A[1]] = c1[2*A[1]] = 1 ;19 for (int k = 2 ; k <= N ; ++ k) {20 for (int i = 0 ; i <= sum*2 ; ++ i) {21 for (int j = 0 ; j <= 2 && (i+j*A[k] <= sum*2) ; ++ j)22 c2[i+j*A[k]] += c1[i] ;23 }24 for (int i = 0 ;i <= sum*2 ; ++ i) c1[i] = c2[i] , c2[i] = 0 ;25 }26 int ans[10010] , cnt = 0 ;27 for (int i = sum + 1 ; i <= sum*2 ; ++ i) if (c1[i] == 0) ans[++cnt] = i - sum ;28 printf("%d\n",cnt);29 for (int i = 1 ; i <= cnt ; ++ i) {30 if (i == cnt) printf("%d\n",ans[i]);31 else printf("%d ",ans[i]);32 }33 }34 return 0 ;35 }
~end~