> 
> //三维数组的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;
> 	}
> 	
> }