原題鏈接 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的組合數,實際上這個問題類似于完全背包新聞熱點
疑難解答
