papamelong 306. 捡苹果 Apple Catching（挑战程序设计竞赛）

地址 https://www.papamelon.com/problem/306

样例 1
输入
7 2
2
1
1
2
2
1
1
输出
6

解答

动态规划
dp[x][y][z] 表示 第x分钟移动y次在z的树下能得到最大的苹果

 
#include 
#include 
#include 
using namespace std;

const int N = 1010;
const int M = 35;
int dp[N][M][3];

/*
7 2
2
1
1
2
2
1
1
*/

int t, w;
int tree[N];

int main()
{
	cin >> t >> w;
	for (int i = 1; i <= t; i++) {
		cin >> tree[i];
	}

	for(int j = 0;j < N;j++){
		for (int i = 0; i < M; i++) {
			dp[j][i][1] = -9999999;
			dp[j][i][2] = -9999999;
		}
	}

	dp[0][0][1] = 0;

	for (int i = 1; i <= t; i++) {
		for (int j = 0; j <= w; j++) {
			if (tree[i] == 1) {
				dp[i][j][1] = dp[i - 1][j][1] + 1;
				dp[i][j][2] = dp[i - 1][j][2];
				if (j >= 1) {
					dp[i][j][1] = max(dp[i][j][1], dp[i-1][j-1][2]+1);
				}
			}
			else {
				dp[i][j][1] = dp[i - 1][j][1];
				dp[i][j][2] = dp[i - 1][j][2] + 1;
				if (j >= 1) {
					dp[i][j][2] = max(dp[i][j][2],dp[i-1][j-1][1]+1);
				}
			}
		}
	}

	int ans = -1;
	for (int i = 0; i <= w; i++) {
		ans = max(ans, dp[t][i][1]);
		ans = max(ans, dp[t][i][2]);
	}
	cout << ans << endl;

	return 0;
}

我的视频题解空间