首页 > 代码库 > POJ3181
POJ3181
Dollar Dayz
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 3923 | Accepted: 1530 |
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$1Write 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
5 3
Sample Output
5
Source
就是整数划分的模板题,只是输出的结果比较打,高精度用数组储存。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;const __int64 MD=10000000000;struct node{ __int64 g[5]; node friend operator +(node a,node b) { node c; int i; for(i=0;i<5;i++) { c.g[i]=a.g[i]+b.g[i]; } for(i=0;i<5;i++) { if(c.g[i]>=MD) { c.g[i+1]+=c.g[i]/MD; c.g[i]%=MD; } } return c; } void friend shuchu(node a) { int i; for(i=4;i>=0&&a.g[i]==0;i--); printf("%I64d",a.g[i]); for(i--;i>=0;i--) { printf("%010I64d",a.g[i]); } printf("\n"); }};node dp[1001][101];int main(){ int n,k,i,j,x; for(i=0;i<1001;i++) for(j=0;j<101;j++) for(x=0;x<5;x++) dp[i][j].g[x]=0; for(i=1;i<1001;i++) dp[i][1].g[0]=1; for(i=1;i<101;i++) dp[1][i].g[0]=1; dp[0][0].g[0]=1; for(i=2;i<1001;i++) { for(j=2;j<101;j++) { if(i==j) dp[i][j]=dp[i][i-1]+dp[0][0]; else if(i<j) dp[i][j]=dp[i][i]; else dp[i][j]=dp[i][j-1]+dp[i-j][j]; } } //cout<<dp[5][3].g[0]<<endl; while(scanf("%d%d",&n,&k)!=EOF) { shuchu(dp[n][k]); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。