poj3181Dollar Dayz(完全背包+记录组合种数+高精度) - c++编程基础

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

5 3

Sample Output

题目意思：就是给出二个数N，和k，有1~k种钱币，每种都是无限个，用这些种类的钱币可以组合成总钱N有多少种方式。

解题：这就是一个完全背包，把N看成容量，钱币的类型值为花费和价值。与记录有多少种路径的走法一样，但要注意的是这里输出的数据会很大，会超出long long型，所以用两个long long 型来表示一个大数。分别是高位和低位，低位不超过10^18，也就是有17位数。

#include
   
    
int N,dp1[1005];
__int64 dp[2][1005],c,mm;
void complexepack(int use)
{
    for(int n=use;n<=N;n++)
    if(dp1[n]
    
     0) { for(int i=0;i<=N;i++) { dp[0][i]=dp[1][i]=0; dp1[i]=0; } dp[0][0]=1; for(int v=1;v<=k;v++) complexepack(v); if(dp[1][N]) printf("%I64d%017I64d\n",dp[1][N],dp[0][N]); else printf("%I64d\n",dp[0][N]); } }