POJ 3181 Dollar Dayz 题解 《挑战程序设计竞赛(第2版)》

POJ 3181 Dollar Dayz

农夫约翰有N元钱，市场上有价值1……K的商品无限个，求所有的花钱方案？

这是一个完全背包问题和大数的混合题目。

《2.3 记录结果再利用的“动态规划” 优化递推关系式》练习题的第三题。

定义 

dp[i][j] := 用i种价格配出金额j的方案数。

那么dp[i][0] = 1，使用任何价格配出金额0的方案个数都是1（什么都不用）。

递推关系式：

dp[i][j] = dp[i – 1][j] + dp[i – 1][j – i] + dp[i – 1][j – 2 * i] + … + dp[i – 1][0]

解释一下，dp[i][j] += 所有dp[i – 1][x]之和，其中x为比j小i的整数倍的数。我这种“中文伪码”描述得很别扭，拿用例举个栗子吧：

dp[2][5] = dp[1][5] + dp[1][3] + dp[1][1];

于是初步的代码：

#include <iostream>
using namespace std;

unsigned long long dp[100 + 16][1000 + 16];	// dp[i][j] := 用i种价格配出金额j的方案数

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int N, K;
	cin >> N >> K;
	dp[0][0] = 1;
	for (int i = 1; i <= K; ++i)
	{
		for (int k = 0; k <= N; k += i)
		{
			for (int j = N; j >= k; --j)
			{
				dp[i][j] += dp[i - 1][j - k];
			}
		}
	}
	cout << dp[K][N] << endl;
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

上面这份代码提交后报WA，换用 unsigned long long 依然WA，猜测是大数。嘛，那就实现一个简易的大数加法吧，原本用一个 unsigned long long 的地方改用两个，分别表示低位和高位。由于 unsigned long long 最大范围到 1844674407370955161 ，所以取一个比这个值小一个数量级同时又能被10整除的数作为limit，得出下面这份AC代码：

#include <iostream>
using namespace std;

// 0高位 1低位
unsigned long long dp[100 + 16][1000 + 16][2];	// dp[i][j] := 用i种价格配出金额j的方案数
#define LIMIT_ULL 100000000000000000

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int N, K;
	cin >> N >> K;
	dp[0][0][1] = 1;
	for (int i = 1; i <= K; ++i)
	{
		for (int k = 0; k <= N; k += i)
		{
			for (int j = N; j >= k; --j)
			{
				dp[i][j][0] += dp[i - 1][j - k][0];
				dp[i][j][1] += dp[i - 1][j - k][1];
				// 高位进位
				dp[i][j][0] += dp[i][j][1] / LIMIT_ULL;
				// 低位限制
				dp[i][j][1] = dp[i][j][1] % LIMIT_ULL;
			}
		}
	}
	if (dp[K][N][0])
	{
		cout << dp[K][N][0];
	}
	cout << dp[K][N][1] << endl;
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

不过上面这份代码并非最优的，如果碰上了男人八题那种测试数据的话肯定会TLE吧。

为何说它不是最优的，因为在递推关系式中

dp[i][j] = dp[i – 1][j] + dp[i – 1][j – i] + dp[i – 1][j – 2 * i] + … + dp[i – 1][0]

将j换成j – i有

dp[i][j – i] = dp[i – 1][j – i] + dp[i – 1][j – 2 * i] + … + dp[i – 1][0]

于是就有：

dp[i][j] = dp[i – 1][j] + dp[i][j – i]

于是可以省掉一重循环，将复杂度降低到O(NK)。

……好冷，先去烤个火，指头冻僵了……

好的，优化递推关系式之后的代码：

#include <iostream>
using namespace std;

// 0高位 1低位
unsigned long long dp[100 + 16][1000 + 16][2];	// dp[i][j] := 用i种价格配出金额j的方案数
#define LIMIT_ULL 100000000000000000

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int N, K;
	cin >> N >> K;
	for (int i = 1; i <= K; ++i)
	{
		dp[i][0][1] = 1;
		for (int j = 1; j <= N; ++j)
		{
			if (j < i)
			{
				dp[i][j][0] = dp[i - 1][j][0];
				dp[i][j][1] = dp[i - 1][j][1];
			}
			else
			{
				dp[i][j][0] = dp[i - 1][j][0] + dp[i][j - i][0];
				dp[i][j][1] = dp[i - 1][j][1] + dp[i][j - i][1];
				// 高位进位
				dp[i][j][0] += dp[i][j][1] / LIMIT_ULL;
				// 低位限制
				dp[i][j][1] = dp[i][j][1] % LIMIT_ULL;
			}
		}
	}

	if (dp[K][N][0])
	{
		cout << dp[K][N][0];
	}
	cout << dp[K][N][1] << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

这份代码速度比上一份快了一个数量级。

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3181 Dollar Dayz 题解 《挑战程序设计竞赛(第2版)》