ICPC国内予選2016 D問題 : ダルマ落とし

問題. ダルマ落とし

正整数 $w_1, w_2, \ldots, w_n$ が与えられる．隣り合う2要素で値の差の絶対値が1以下ならばその2要素を取り除くことができる．最大でいくつの要素を取り除くことができるかを求めよ．

制約： $1 \le n \le 300$ ，　 $1 \le w_i \le 1,000$

解法. 区間DP

この問題を，状態を区間で持つ動的計画法(Dynamic Programming; DP)で解く．競プロの世界ではこのような動的計画法を区間DPと呼ぶらしい．

解の性質について考察する。 $i < j$ に対して $w_i$ と $w_j$ を取り除くことができるなら $\left|w_i - w_j \right| \le 1$ かつ $w_{i+ 1}, w_{i + 2}, \ldots, w_{j - 1}$ が既に取り除かれている。したがって、 $i_1 < i_2 < i_3 < i_4$ に対して $w_{i_1}$ と $w_{i_3}$ 、 $w_{i_2}$ と $w_{i_4}$ がそれぞれペアとして取り除かれることはないので、どの解も交差しない区間に分割することができる。
例えば、 $(8, 7, 1, 4, 3, 5, 4, 1, 6, 8, 10, 4, 6, 5)$ の最適解の一つは $[8, 7, 1, 4, 3, 5, 4, 1, 6, 8] [10] [4, 6, 5]$ と 3 つの部分区間に分割して各部分区間の最適解を連結させたものと等しい。以上から、区間を状態に持つ動的計画法が下のように構成できる。

次のように区間を引数にとる関数を考える．
　 $f(i, j) := 区間 [i, j]$ のときに取り除くことができる要素の最大数
このとき， $f(i, j)$ が $j - i + 1$ に等しいとき区間 $[i, j]$ の要素を全て取り除くことが出来るということになる．ここで， $f(i, j)$ の漸化式は，
　 ${ \begin{eqnarray} f(i, j) = \left\{ \begin{array}{ll} j - i + 1 & \left(f(i + 1, j - 1) が j - i - 1 に等しく，\\かつ \left|w_i - w_j\right| \le 1のとき\right) \\ \max\{f(i, k - 1) + f(k, j) \mid i + 1 \le k \le j \} & (それ以外のとき) \end{array}\right. \end{eqnarray} }$
となる．あとは，区間のサイズが小さい方から上の漸化式を計算すればよい．

計算時間： $O(n^3)$

ソースコードを表示

#include <iostream>
#include <vector>

using namespace std;

int SolveDaruma(const vector<int> &w) {
    const int size = w.size();
    vector<vector<int>> dp(size, vector<int>(size));
    for (int l = 0; l + 1 < size; ++l)
        if (abs(w[l] - w[l + 1]) <= 1)
            dp[l][l + 1] = 2;

    for (int n = 3; n <= size; ++n) {
        for (int l = 0; l + n <= size; ++l) {
            const int r = l + n - 1;

            if (abs(w[l] - w[r]) <= 1 && dp[l + 1][r - 1] == n - 2) {
                dp[l][r] = n;
                continue;
            }

            for (int m = l + 1; m <= r; ++m) // 区間 [l, m), [m, r] に分割
                dp[l][r] = max(dp[l][r], dp[l][m - 1] + dp[m][r]);
        }
    }
    return dp[0].back();
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    while (cin >> n, n) {
        vector<int> w(n);
        for (auto &w_i : w) cin >> w_i;

        cout << SolveDaruma(w) << '\n';
    }

    return 0;
}