原题链接 Dollar Dayz Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6768 Accepted: 2538 Description
Farmer John goes to Dollar Days at The Cow Store and discovers an unlimited number of tools on sale. During his first visit, the tools are selling variously for
Write a PRogram than will compute the number of ways FJ can spend N dollars (1 <= N <= 1000) at The Cow Store for tools on sale with a cost of
A single line with two space-separated integers: N and K. Output
A single line with a single integer that is the number of unique ways FJ can spend his money. Sample Input
5 3 Sample Output
5 Source
USACO 2006 January Silver
#include <cstdio>#include <cstring>#include <iostream>using namespace std;typedef long long ll;const int maxn = 1010;const int maxk = 110;ll a[2][maxn],b[2][maxn];//2^63~=9*10^18,所以用a数组表示前18位数，用b数组表示后18位数int main(){ int n,k; cin >> n >> k; b[0][0] = b[1][0] = 1; ll mod=1; for(int i=0;i<18;i++) mod*=10; for(int i=1;i<=k;i++){ for(int j=1;j<=n;j++){ if(j-i>=0){ a[i&1][j] = a[(i-1)&1][j] + a[i&1][j-i] + (b[(i-1)&1][j] + b[i&1][j-i])/mod; b[i&1][j] = (b[(i-1)&1][j] + b[i&1][j-i])%mod; } else{ a[i&1][j] = a[(i-1)&1][j]; b[i&1][j] = b[(i-1)&1][j]; } } // for(int j=0;j<=n;j++){ // if(a[i&1][j]) cout << a[i&1][j]; // cout << b[i&1][j] << " "; // } // cout << endl; } if(a[k&1][n]) cout << a[k&1][n]; cout << b[k&1][n] << endl; return 0;}// #include <cstdio>// #include <cstring>// #include <iostream>// using namespace std;// const int maxn = 1010;// const int maxk = 110;// int dp[2][maxn];// int main(){// int n,k;// cin >> n >> k;// dp[0][0] = dp[1][0] = 1;// for(int i=1;i<=k;i++){// for(int j=1;j<=n;j++){// if(j-i>=0) dp[i&1][j] = dp[(i-1)&1][j] + dp[i&1][j-i];// else dp[i&1][j] = dp[(i-1)&1][j];// }// // for(int j=0;j<=n;j++) printf("%2d ",dp[i&1][j]);// // cout << endl;//解决的思路是对的，只是数据范围太大已经超出了long long这个样子// }// cout << dp[k&1][n] << endl;// return 0;// }//多重集组合数是问总共取出k个数总共有多少种组合数，并且每种数都有数量限制，但是这里却没有//，而且问得是组成数k的组合数,实际上这个问题类似于完全背包新闻热点
疑难解答
