itdef

地址 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 <iostream>
#include <algorithm>
#include <memory.h>
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;
}

動態規劃
dp動態規劃方案
dp[i][j][k] 表示當前在第i棵樹下經過了時間j移動次數為k 能得到的最大蘋果數

dp[i][j][k]可能從以下路徑轉移過來
1 原地不動
那么只有時間變化了單位1
dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]);

2 從另一棵樹移動過來
時間變化了單位1 樹的索引變化1->2或者2->1 移動次數+1
dp[i][j][k] = max(dp[i][j][k], dp[1->2||2->1][j-1][k-1]);

如果當前掉落的果子樹索引和站立的樹的索引一直 則拿到該蘋果 dp[i][j][k]+1

#include <iostream>
#include <memory.h>
using namespace std;

int dp[3][1005][35];
int t, w;
int a[1005];

void solve() {
	for (int i = 1; i <= t; i++) cin >> a[i];

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

				dp[2][i][k] = dp[2][i - 1][k];
			}
			else {
				dp[2][i][k] = dp[2][i - 1][k] ;
				if (k > 0) {
					dp[2][i][k] = max(dp[2][i][k],dp[1][i-1][k-1]);
				}
				dp[2][i][k] += 1;

				dp[1][i][k] = dp[1][i - 1][k];
			}
		}
	}

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

int main()
{
	while (~scanf("%d%d", &t, &w)) {
		memset(a,0,sizeof a);
		memset(dp, -0x3f, sizeof dp);
		dp[1][0][0] = 0;

		solve();
	}
	return 0;
}

我的視頻題解空間