题目大意：
给你n元钱和无限个价钱为1~k的物品，让你求有多少种方法花光这n元钱？
思路：
参考别人的。。
可以看成是整数的划分。
如5 3
1+1+1+1+1
1+1+1+2 1+2+2
1+1+3 2+3
设dp[i][j]为i的划分中最大数不超过j的划分总数。
则dp[i][j]=dp[i][j-1]+dp[i-j][j];
有点像组合的某个公式。
最大数不选j即最大数为J-1的个数+最大数选中了j，即dp[i-j][j]。
值得一提的是结果可能会很大，看到大神的思路是这样的，用两个__int64的整数来模拟高精度。
把一个数拆成两个。
Orz。。
#include#include const int MAXN=1000+10; __int64 a[MAXN][MAXN],b[MAXN][MAXN],mod=1; //dp[i][j]为i的划分中最大数为j的数目 int main() { int n,k; for(int i=1;i<=18;i++) mod*=10; while(~scanf(%d%d,&n,&k)) { memset(b,0,sizeof(b)); memset(a,0,sizeof(a)); for(int i=0;i<=k;i++) a[0][i]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=k;j++) { if(i >= j ) { a[i][j]=(a[i][j-1] + a[i-j][j])%mod; //后面的位数 b[i][j]=b[i][j-1]+b[i-j][j] +(a[i][j-1] + a[i-j][j])/mod;//前面的位数 } else { a[i][j]=a[i][j-1]; b[i][j]=b[i][j-1]; } } } if(b[n][k]) printf(%I64d,b[n][k]); printf(%I64d ,a[n][k]); } return 0; }