POJ 3181 Dollar Dayz 动态规划法题解

Description

        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

Input

Output

Sample Input

5 3

Sample Output

5

Source

本题也是一种背包问题，就是需要求出有多少种组合。

本题的新意就是：

1 利用两个long long数表示大数的高位和低位就能满足不溢出了

2 高位和低位需要仔细计算好

建模：

dp[i][j]：表示计算当前i物品的时候有j钱币的时候有多少种组合。

那么状态转换：dp[i][j] = dp[i-1][j] + dp[i][j-i]//dp[i-1][j]表示前一种物品计算出的组合数，也就是不买i物品的组合数， dp[i][j-i]表示空出i钱币购买i物品的组合数

难点：

仔细观察，会发现其实不单止不用二维数组，就连滚动数组都不需要使用。

如下面程序，直接使用一维数组就能得到答案了。

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <limits.h>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;

const int MAX_N = 1001;
long long hiBit[MAX_N], lowBit[MAX_N];
const long long MOD = (long long) 1E18;//lowBit保存18个0，为了输出格式一致，之后就要进位了，其中long long可以保存19位数

void getCombinations(int N, int K)
{
	memset(hiBit, 0, sizeof(long long) * (N+1));
	memset(lowBit, 0, sizeof(long long) * (N+1));
	lowBit[0] = 1LL;
	for (int i = 1; i <= K; i++)
	{
		for (int j = i; j <= N; j++)
		{
			lowBit[j] += lowBit[j-i];//买和不买i物品的和，就是当前组合和了
			hiBit[j] += lowBit[j] / MOD + hiBit[j-i];//错误：忘记hiBit[j-i]
			lowBit[j] %= MOD;//保存低位
		}
	}
}

int main()
{
	int N, K;
	while (~scanf("%d %d", &N, &K))
	{
		getCombinations(N, K);
		if (hiBit[N] > 0LL) printf("%lld", hiBit[N]);
		printf("%lld\n", lowBit[N]);
	}
	return 0;
}

POJ 3181 Dollar Dayz 动态规划法题解

原文：http://blog.csdn.net/kenden23/article/details/41695331