Time Limit: 5 Sec Memory Limit: 64 MB
[Submit][Status][Discuss]
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 $1, $2, and $3. Farmer John has exactly $5 to spend. He can buy 5 tools at $1 each or 1 tool at $3 and an additional 1 tool at $2. Of course, there are other combinations for a total of 5 different ways FJ can spend all his money on tools. Here they are: 1 @ US$3 + 1 @ US$2 1 @ US$3 + 2 @ US$1 1 @ US$2 + 3 @ US$1 2 @ US$2 + 1 @ US$1 5 @ US$1 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 $1..$K (1 <= K <= 100).
Input
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
Sample Output
HINT
Source
Silver
Solution
这题是简单的背包问题，要用高精度。我用了运算符重载。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<iostream> #include<cstdio> using namespace std; int n,k; struct bign{ int f[100];}a[1005]; bign operator +(bign a,bign b) { bign c; for (int i=1;i<=100;i++) c.f[i]=0; for (int i=1;i<100;i++) { c.f[i]+=a.f[i]+b.f[i]; if (c.f[i]>=10) c.f[i+1]+=c.f[i]/10,c.f[i]%=10; } return c; } int main() { scanf("%d%d",&n,&k); a[0].f[1]=1; for (int i=1;i<=k;i++) for (int j=i;j<=n;j++) a[j]=a[j]+a[j-i]; int len; for (int i=1;i<=100;i++) if (a[n].f[i]>0) len=i; for (int i=len;i>=1;i--) printf("%d",a[n].f[i]); printf("\n"); return 0; } |
