返回信息流原题描述为You may assume that all the amounts are positive and less than 2000.
但是我在将数组上界设为2000时结果为WA，而改为2001时AC了，说明至少有一组测试数据其中包含2000，而并非less than 2000
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #92633同步于 2017/3/28
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
3-28网络热身赛B题是否描述有误
Nroskill
2017/3/28镜像同步8 回复
订阅后，新回复会通过你的通知中心匿名送达。
8 条回复
用动态规划的思路做的，维护一个数组count[17][2001]，count[i][j]的值表示，使用第i到第17种货币，有多少种拼法可以拼出j。
【 在 yjc120592 的大作中提到: 】
: 请教楼主此题的思路，谢谢啦～
我的方法更好一点
int main(){
vector<int> pool(2001,1);
for(int i=2;i!=17+1;++i){
for(int k=i*i;k<2001;++k){
pool[k] = (pool[k] + pool[k-i*i])%1000000009;
}
}
cin>>T;
for(int time=0;time!=T;++time){
cin>>n;
cout<<pool[n]<<endl;
}
return 0;
}
【 在 Nroskill 的大作中提到: 】
: 用动态规划的思路做的，维护一个数组count[17][2001]，count[i][j]的值表示，使用第i到第17种货币，有多少种拼法可以拼出j。
:
6666，思路确实巧妙，我一开始也想到用一维的，但是二维的已经写一半了（习惯二维的思路了orz），就没换。要是我写估计会把你这两个循环位置倒置一下，然后判断n > 0什么的，没有你这个精炼。
【 在 duduscript 的大作中提到: 】
: 我的方法更好一点
: [code=c]
: int main(){
: ...................