http://acm.hdu.edu.cn/showproblem.php?pid=1398
//1304230 2009-04-24 14:13:00 Accepted 1398 0MS 260K 523 B C++ no way
#include<iostream>
using namespace std;
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) int squares[17]= {1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289};
//所有硬币的种类及面值
int i,j,k;
int num[301],temp[301];
for(i=0;i<=300;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
num[i] = 1;
temp[i] = 0;
}
for(i=2; i<=17; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(j=0;j<=300;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(k=0 ; k+j<=300; k+=squares[i-1])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
temp[j+k] += num[j];
}
}
for (j=0;j<=300;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
num[j] = temp[j];
temp[j]=0;
}
}
while(cin>>k && k)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
cout<<num[k]<<endl;
}
return 0;
}
|