sdut 2934 人活着系列之平方数 (完全背包变形)

分析：完全背包的变形，每一层的d[]数组代表这一层的这个数新加入以后所构成的val的种类。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #include <cstdlib>
 6 #include <algorithm>
 7 const int maxn = 500+10;
 8 using namespace std;
 9 int d[maxn], a[30];
10 
11 int main()
12 {
13     int n, i, j;
14     while(~scanf("%d", &n))
15     {
16         for(i = 1; i <= 20; i++)
17         a[i] = i*i;
18         memset(d, 0, sizeof(d));
19         for(i = 0; i <= n; i++)  //z注意要把0也加上，不让会少了被本身构成的这种情况
20         d[i] = 1;
21 
22         for(i = 2; i <= 20; i++)
23         for(j = a[i]; j <= n; j++)
24         d[j] = d[j] + d[j-a[i]];
25 
26         printf("%d
", d[n]);
27     }
28     return 0;
29 }