//三维数组的DP
//所有数据都是从数组下标1开始的,但是由于在一开始牛可以花费一次移动到另一个树下,故判断从下标0开始
#include <iostream>
using namespace std;


int aa[2][1002][31];//表示在即将面对 在树[x]下,时间[t]下,剩余[r]次移动 的情况时,最多能吃几个苹果
bool yon[2][1002][31];//记录[][][]点是否已被运算过

int NT = 0, W = 0;//总时间,总移动次数
int tj[2][1002];//用于记录 树[x]将在时间[t] 落下 0个还是1个 苹果

int getvalue(int p, int T, int rw);

int main()
{
	int lw = 0;//临时变量,用来接收某一时刻落下苹果的是哪棵树

	memset(aa, 0, sizeof(aa));//全都初始化为 0 
	memset(yon, 0, sizeof(yon));
	memset(tj, 0, sizeof(tj));

	scanf_s("%d%d", &NT, &W);//输入总时间,总移动次数

	for (int i = 1; i <= NT; i++)
	{
		scanf_s("%d", &lw);
		if (lw == 1)//如果 i 时刻是 树1 落下苹果,那么就将 tj[0][i]设为 1 ,代表此时落下 1 个苹果,由于 tj 被初始化为 0 了，所以此时 树2 落下的苹果数为0
		{
			tj[0][i] = 1;
		}
		else//同理
		{
			tj[1][i] = 1;
		}
	}

	for (int i = 0; i < 2; i++)//当在总时间以后,不会再获取苹果,故将这些情况的 dp 视为 0 ,并标记为已被运算过,使此三维数组封闭
	{
		for (int j = 0; j < 31; j++)
		{
			yon[i][NT + 1][j] = true;
		}
	}

	printf_s("%d", getvalue(0, 0, W));

	return 0;
}

int getvalue(int p, int T, int rw)
{
	if (yon[p][T][rw])
	{
		return aa[p][T][rw];
	}
	yon[p][T][rw] = true;//将此点设为已被运算过的状态

	int a = getvalue(p, T + 1, rw) + tj[p][T];
	int b = 0;
	if (rw)//如果还剩的有移动力,就获取移动到另一棵树的情况,否则 b 将等于初始化时赋予的 0
	{
		b = getvalue(!p, T + 1, rw - 1) + tj[!p][T];
	}

	if (a > b)
	{
		aa[p][T][rw] = a;
		return a;
	}
	else
	{
		aa[p][T][rw] = b;
		return b;
	}
	
}

• Re:典型的动态规划,附模板代码并有详细解析 (1567) 1001010010 2020-01-29 01:40:24