このブログの「区間 DP」タグを充実させたい。この問題は本当に典型的な区間 DP なのでちょうどいい！！！

問題概要

長さ $N$ の整数数列 $a_{1}, \dots, a_{N}$ が与えられる。これらに対して以下の操作を好きな順序で好きな回数だけ行う。

値の差が 1 以下であるような、隣接する 2 つの要素を選び、2 つまとめて削除する

操作によって削除される要素の個数の最大値を求めよ。

制約

$1 \le N \le 300$

考えたこと

この手の「列の中の隣接する 2 項について処理を順次行う」というタイプの問題に対しては

スタックを用いたシミュレーション
区間 DP

といった手法が有効であることが多い。前者の例として「カッコ列の整合性判定」、後者の例として「最適行列積計算を求める DP」が有名だ。今回は後者のパターンになる。

dp[ i ][ j ] := 数列の区間 [i, j) に対して操作を施せる回数の最大値

としておく。このように区間 [i, j) をキーにもつような DP を区間 DP とよぶ人が多い。

区間 DP

さて、dp の遷移を作る上で、以下の 2 つの場合に分けられる。

ある k が存在して、区間 [i, k) と区間 [k, j) とは独立に操作したものとみなせる場合
区間 [i+1, j-1) の要素が無事すべて消滅し、要素 a[ i ] と a[ j - 1 ] のみが残る場合

前者は簡単だ

chmax(dp[ i ][ j ], dp[ i ][ k ] + dp[ k ][ j ])

とかで OK。後者はまず dp[ i + 1 ][ j - 1 ] = j - i - 2 であることが必要だ。その元で

a[ i ] == a[ j - 1 ] ならば、chmax(dp[ i ][ j ], j - i)
a[ i ] != a[ j - 1 ] ならば、chmax(dp[ i ][ j ], j - i - 2)

という感じだ。計算量は $O(N^{3})$ 。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int N;
vector<int> w;

int solve() {
    vector<vector<int>> dp(N+1, vector<int>(N+1, -N));
    for (int i = 0; i <= N; ++i) {
        dp[i][i] = 0;
        if (i < N) dp[i][i+1] = 0;
    }
    for (int bet = 2; bet <= N; ++bet) {
        for (int i = 0; i + bet <= N; ++i) {
            int j = i + bet;
            if (dp[i+1][j-1] == j-i-2) {
                if (abs(w[i] - w[j-1]) <= 1) chmax(dp[i][j], j-i);
                else chmax(dp[i][j], j-i-2);
            }
            for (int k = i+1; k <= j-1; ++k) {
                chmax(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
    return dp[0][N];
}

int main() {
    while (cin >> N, N) {
        w.resize(N);
        for (int i = 0; i < N; ++i) cin >> w[i];
        cout << solve() << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 1611 ダルマ落とし (ICPC 国内予選 2016 D) (400 点)

問題概要

制約

考えたこと

区間 DP