POJ 2385 Apple Catching 题解 《挑战程序设计竞赛(第2版)》

2.3 记录结果再利用的“动态规划” 基础的动态规划算法

POJ 2385 Apple Catching

2棵苹果树在T分钟内随机由某一棵苹果树掉下一个苹果，奶牛站在树#1下等着吃苹果，它最多愿意移动W次，问它最多能吃到几个苹果。

定义dp[x][y][z]表示第x + 1分的时候经过y次移动站在了z+1树下能吃到的最大苹果数，然后搜索所有的xyz组合，更新dp。

#include <iostream>
#include <algorithm>
using namespace std;

int tree[1000];
int dp[1000][32][2]; // dp[x][y][z]表示第x + 1分的时候经过y次移动站在了z+1树下能吃到的最大苹果数

inline int move(const int &k)
{
	return k == 0 ? 1 : 0;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int T, W;
	cin >> T >> W;
	for (int i = 0; i < T; ++i)
	{
		int t;
		cin >> t;
		tree[i] = t - 1;
	}
	if (tree[0] == 0)
	{
		dp[0][0][0] = 1;
	}
	else
	{
		dp[0][1][1] = 1;
	}
	for (int i = 0; i < T - 1; ++i)
	{
		for (int j = 0; j <= W; ++j)
		{
			for (int k = 0; k < 2; ++k)
			{
				if (k == tree[i + 1])
				{
					// 下一个苹果掉在当前树下，那么下一分钟？
					// 站着不动吃一个
					dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + 1);
					// 移动没吃到，不变
					dp[i + 1][j + 1][move(k)] = max(dp[i + 1][j + 1][move(k)], dp[i][j][k]);
				}
				else
				{
					// 下一个苹果掉在另一树下，那么下一分钟？
					// 站着不动没吃到
					dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
					// 移动吃一个
					dp[i + 1][j + 1][move(k)] = max(dp[i + 1][j + 1][move(k)], dp[i][j][k] + 1);
				}
			}
		}
	}

	cout << *max_element(dp[T - 1][0], dp[T - 1][0] + (W + 1) * 2) << endl;
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

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