[215]ワインの試飲

アルゴリズムの実力が悪すぎるようです...
初级问题を久しぶりに复习して解答して今も足踏みしている感じ...ううう
アルゴリズムは暗記よりも原理を考え続ける必要があり、この過程は難しい...
この問題は典型的に連続性の問題を話している.

2 Dアレイ

2 D配列で解きます.
dp[i][j]=>i号で飲用されたワインの中で、j号を連続して飲む場合、最も大量に入っています.
1)dp[i][0]->0回連続飲用.iを選択していないという意味です.したがって、前のi−1の最大値が格納される.
2)dp[i][1]->1回飲み続けます.すなわち,iを選択し,i−1を選択しなかった.したがって、dp[i−1][0]+a[i]に等しい.
3)dp[i][2]->2回連続で飲む.すなわち,i,i−1を選択し,i−2を選択しなかった.したがって、dp[i−1][1]+a[i]に等しい.
コードは次のとおりです.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<set>
#include<cstdlib>
#include<sstream>
using namespace std;
long long  dp[10001][3];
int a[10001];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, k;
	cin >> n;
	long long  maxx = -1;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		
	}
	dp[1][0] = 0;
	dp[1][2] = 0;
	dp[1][1] = a[1];
	for (int i = 2; i <= n; i++) {
		dp[i][0] = max(max(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]);
		dp[i][1] = dp[i - 1][0] + a[i];
		dp[i][2] = dp[i - 1][1]+ a[i];
	}

	for (int i = 0; i <= 2; i++) {
		maxx = max(dp[n][i], maxx);
		//cout << dp[n][i] <<' ';
	}
	cout << maxx;
	return 0;
}

1 Dアレイ

1 Dアレイで解くこともできます.
dp[i]をiまで飲むと、ワインの最大量に指定されます.
1)0回連続(=i回飲まない)でd[i-1]に等しい.
2)連続1回(i回飲んでi-1回飲まない)dp[i-2]+a[i]
3)連続2回(i,i-1回、i-2回飲まない)dp[i-3]+a[i]+a[i-1]
その中の最大値を求めればいい.