放牧代码和思想
专注自然语言处理、机器学习算法

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//////////////////////////////////
12507590 hankcs 3181 Accepted 1856K 500MS C++ 1025B 2014-02-09 20:58:50

不过上面这份代码并非最优的,如果碰上了男人八题那种测试数据的话肯定会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//////////////////////////////////

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

12507823 hankcs 3181 Accepted 1856K 16MS C++ 1108B 2014-02-09 22:24:47

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

分享到:更多 ()

评论 3

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #2

    dp += 所有dp 这里有个笔误 是 i-1.

    窗旁的yeben2年前 (2015-08-20)回复
  2. #1

    谢谢!看书理解那个优化递推方程式很久没有彻悟,今天看了真是醍醐灌顶!

    窗旁的yeben2年前 (2015-08-20)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机