門松計画 [yukicoder No.783] - はまやんはまやんはまやん

前提知識

動的計画法

解説

dpで解く。
dp[len][prepre][pre][c] := 長さlenの門松列列であり2つ前の竹がprepreで1つ前の竹がpreであり、お金の残高がc円であるときの長さの総和の最大値
最初の2つは予め作っておくことにした。
dp[len][prepre][pre][c]からN択の遷移をする。
次の竹としてnxtを採用するとすると、竹prepre, 竹pre, 竹nxtが門松列であるか確かめる。
門松列でお金も足りるなら採用する。
あとは、DP全体を見て、最大値を探すと答え。

int N, C, L[50], W[50];
// dp[len][prepre][pre][c]
int dp[51][51][51][51];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> C;
    rep(i, 0, N) cin >> L[i];
    rep(i, 0, N) cin >> W[i];

    rep(a, 0, N) rep(b, 0, N) if (L[a] != L[b] and W[a] + W[b] <= C) dp[2][a][b][C - W[a] - W[b]] = L[a] + L[b];

    rep(len, 2, C) rep(prepre, 0, N) rep(pre, 0, N) rep(c, 0, C) if (0 < dp[len][prepre][pre][c]) {
        rep(nxt, 0, N) if (L[prepre] != L[nxt] and L[pre] != L[nxt]) {
            if (L[prepre] < L[pre] and L[pre] > L[nxt] and 0 <= c - W[nxt]) {
                chmax(dp[len + 1][pre][nxt][c - W[nxt]], dp[len][prepre][pre][c] + L[nxt]);
            }
            if (L[prepre] > L[pre] and L[pre] < L[nxt] and 0 <= c - W[nxt]) {
                chmax(dp[len + 1][pre][nxt][c - W[nxt]], dp[len][prepre][pre][c] + L[nxt]);
            }
        }
    }

    int ans = 0;
    rep(len, 3, C + 1) rep(prepre, 0, N) rep(pre, 0, N) rep(c, 0, C) chmax(ans, dp[len][prepre][pre][c]);
    cout << ans << endl;
}