DP 2階へ上がる

ステップ

各階段には点数があり、階段があり、各階段は1段、2段、連続して3つ上がることが条件付きの問題です.
これらの条件を整理すると.
1.1グリッドまたは2グリッド移動可能
2.3個連続できない
はい.
たまにワインを飲んだり、他の形をしたりすることもあります.つまりコアはDPプールです.
この問題は大きく二つのパターンに分かれている.

最後の一歩を踏み出すパターン

最後に必ず聞かないと終わらないパターン.白準2579番に相当する.
全部で6つの階段があり、10 20 15 25 10 20は各階段の価格です.
まず第1段階dp[1]の最大値を考慮し、もちろんscore[1]である.(10)
2番目のフェーズでは、scoreが負の値でない場合、dp[1]+score[2]がその値になります.(30)
第3条から、上記でまとめた第2条のルールを適用します.

1.1号階段後3号階段

10 + 15 = 25

2.2号階段後3号階段

20 + 15 = 35
だから35です.
4番目の階段はどうですか.
4つ目も同様で、以下のようになります.

1.2号階段後4号階段

この場合、3連技団は絶対に出ないので、2番までの最大値dp[2]+score[4].

2.1番までの最大値+3番階段後4番階段

3番までの最大値を入力すると、3接続エラーが発生する可能性がありますので、1番までの最大値を+4番までの最大値に設定してください.
では最後の一歩を踏み出したとします(N)

1.n-1を踏んで最後の1つを踏む

dp[n-3]+score[n-1]+score[n].

2.dp[n-1]なし

この場合,無条件にdp[n−2]を踏んで来た.
従ってdp[n−2]+score[n]である.
これを点火式にまとめて以下のようにします.
dp[i] = max((dp[i-3] + score[i-1] + score[i]), dp[i-2] + score[i]);

#include <iostream>
#include <algorithm>
#define MAX 300
using namespace std;

int score[301];
int dp[301];
int n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> score[i];
    }
    dp[0] = 0;
    dp[1] = score[1];
    dp[2] = score[1] + score[2];
    dp[3] = max(score[1], score[2]) + score[3];

    for (int i = 4; i <= n; i++) {
        dp[i] = max((dp[i-3] + score[i-1]), dp[i-2]) + score[i];
    }
    cout << dp[n];
}

コード全体を以下に示します.

最後に通る必要がなければ

白駿2156.
ルールとタイプは同じですが、最後に行く必要はありません.でも今回の問題は階段ではなくワインを飲むことです.△もう飲まないで、孝珠!
ワインは全部で6個あり、6 10 13 9 8 1はワイン1個あたりの容量です.
最初のワインはもちろんscore[1].
2つ目のワインには2つの状況があります.

1杯目、2杯目を飲み続けたら

最初の一杯だけ飲んだら。

2杯目だけ飲んだら。

もちろん、1杯目、2杯目を飲み続ける場合、値段は高いに違いありません.したがって、dp[2]=score[1]+score[2].
では、3杯目はいかがですか.
大きく分けて3杯目と飲まない2種類.

飲まない場合

まず、この場合、三連飲禁止の条項には触れません.従って、この場合、最大飲用量はdp[n−1]である.
これを数式にまとめると以下のようになります.
dp[n] = dp[n-1]

飲用状況

この状況はもっと複雑だ.
OXO
XOO
XXO
全部で3つのケースがあるからです.
まず3つ目のケースは成功するとは限らないが除去すれば
n-2を飲んでnを飲んだり、n-1を飲んでnを飲んだりするのは2つあります.
n-2とnを飲めば、3年間の飲用は禁止されません.従って、dp[n−2]の最大値を用いることができる.
n−1の場合、nを飲むには3つの研磨期間が必要になる可能性がある.したがって,[n−3]の最大値+score[n−1]+score[n]である必要がある.
これを数式に再整理すると以下のようになります.
dp[i] = max(dp[i-3] + score[i-1] + score[i], dp[i-2] + score[i])

#include <iostream>
#include <algorithm>
#define MAX 300
using namespace std;

int score[10001];
int dp[10001];
int n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> score[i];
    }
    dp[0] = 0;
    dp[1] = score[1];
    dp[2] = dp[1] + score[2];
    for (int i = 3; i <= n; i++) {
        dp[i] = max(score[i] + max(dp[i-3] + score[i-1], dp[i-2]), dp[i-1]);
    }
    int max = 0;
    for (int i = 1; i <= n; i++) {
        if (dp[i] > max) max = dp[i];
    }
    cout << max;
}

コード全体を以下に示します.

整理する

以上の2つのタイプがdpといえばこれです!よく見かけるので覚えておいたほうがいいです.