ZOJ 1666 Square Coins

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=666

本来是找背包问题做的. 搜到这题, 结果完全没有背包的思路, 看了别人的题解. 也不觉得是背包.....⊙﹏⊙b汗

View Code

 1 #include <iostream>
 2 #define maxn 305
 3 using namespace std;
 4 int ans[maxn], v[20];
 5 int main()
 6 {
 7     int i, j, m, count;
 8     for(i = 1; i <= 17; i++)
 9     v[i] = i*i;
10     for(i = 0; i <= maxn; i++)
11     ans[i] = 0;
12     ans[0] = 1;
13     for(i = 1; i <= 17; i++)
14      for(j = v[i]; j < maxn; j++)
15      ans[j] += ans[j-v[i]];
16     while(cin >> m, m)
17     {
18         cout << ans[m] << endl;
19     }
20     return 0;
21 }

也许自己对背包的理解还不够到位. .....