首页 > 代码库 > POJ--3181--Dollar Dayz--背包/高精度
POJ--3181--Dollar Dayz--背包/高精度
Dollar Dayz
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 4220 | Accepted: 1642 |
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
题意:输入n,k表示有k种硬币,价值是1~k,求用这些硬币组合出价值n的方案数
解析:数值很大,64位装不下,所以用两个64位的分别充当高位和低位来解决,然后就是完全背包问题了
*******这里有个点我要说,虽然不算错,但是这是题目的漏洞跟思维的严谨,就是当有高位需要输出时一定要把位补起来,一般都是以1E18为摸,所以一般都是有高位就输出高位,接着把低位输出,我说如果低位没有18位整的呢?
拿100来说,高位是1,低位是99,这好,输出来直接就是199,如果低位是9呢?输出的就是19,低位的前导零没有处理啊,有些代码的正确只是建立在数据的不严谨啊。。
#include <iostream>
#include <cstdio>
#include <cstring>
#define Max(a,b) a>b?a:b
using namespace std;
__int64 mod=1000000000000000000;
int main (void)
{
int n,m,i,j,k,l;
__int64 dp[2][1111];
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,0,sizeof(dp));
dp[0][0]=1;
if(m>n)m=n;
for(i=1;i<=m;i++)
for(j=i;j<=n;j++)
{
dp[1][j]=dp[1][j-i]+dp[1][j]+(dp[0][j-i]+dp[0][j])/mod; //高位
dp[0][j]=(dp[0][j-i]+dp[0][j])%mod; //低位
}
if(dp[1][n])
{
printf("%I64d",dp[1][n]);
printf("%018I64d\n",dp[0][n]); //补充前导零
}else
{
printf("%I64d\n",dp[0][n]); //这个不用补充前导零
}
}
return 0;
}
POJ--3181--Dollar Dayz--背包/高精度
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。