题意：有n元钱，商品的价格在1~k元（每种价格的商品数量无限），用n元去买这些商品，最多有多少种选择？
思路：就是最简单的完全背包 (1 <= N <= 1000),(1 <= K <= 100).
也就是说组合数很大 会超出long long范围
对于求完全背包的组合数即从 dp[0] 到dp[n]中出现的可能次数 ，所以令dp[0] = 1 然后动态转移公式 仍是 dp[j] += dp[j-i] ;即自身总数再加上上一次移动的总数
然后数据过大我们就用两个数组来存储，a保存前18位 b保存后18位，用mod运算来取b，/取a （当然还可以尝试使用__int128）;
#include<cstdio> #include<cstring> #define ll long long const ll INF=1e18; //（ll == __int64 ） ll a[1010];//高位 ll b[1010];//低位 int main() { int n,k,i,j; while(scanf("%d%d",&n,&k)!=EOF) { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); b[0]=1; for(i=1;i<=k;++i) { for(j=i;j<=n;++j) { a[j]=a[j]+a[j-i]+(b[j]+b[j-i])/INF; b[j]=(b[j]+b[j-i])%INF; } } if(a[n]==0) printf("%lld ",b[n]); else printf("%lld%018lld ",a[n],b[n]); } return 0; }