区間 DP な問題って、あまり見なくなったなと。貴重なので記録。

問題概要

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

隣接する二項を選び、それらの値が等しいとき (v とする)、その 2 つの値を削除して、代わりに v + 1 に置き換える

一連の操作後の数列の長さの最小値を求めよ。

制約

$1 \le N \le 500$

考えたこと

出た！！！ぷよぷよ的な構造をした問題。ぷよぷよ的な構造とは「列の中の隣接する二項についてどうのこうのする」という雰囲気のこと。有名な「カッコ列の整合性判定」なんかもそう。

そういう問題に対しては

stack を用いてシミュレーション
区間 DP

といった手法が大変有力である。今回は区間 DP がピッタリはまる。区間 DP とはどのようなものかにつては、たとえば以下の問題にある。

atcoder.jp

今回はこんな感じの DP を組んだ

dp[ i ][ j ] := 区間 [i, j) についての、操作後の長さの最小値
val[ i ][ j ] := dp[ i ][ j ] の値が 1 となる場合のみ、そのときの数列の値を記録する

という風にした。計算量は $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; }

const int INF = 1<<29;
int N;
vector<int> a;

long long solve() {
    vector<vector<int>> dp(N+1, vector<int>(N+1, INF));
    vector<vector<int>> val(N+1, vector<int>(N+1, -1));
    for (int i = 0; i < N; ++i) {
        dp[i][i+1] = 1;
        val[i][i+1] = a[i];
    }
    for (int bet = 2; bet <= N; ++bet) {
        for (int i = 0; i + bet <= N; ++i) {
            int j = i + bet;
            for (int k = i+1; k <= j-1; ++k) {
                if (dp[i][k] == 1 && dp[k][j] == 1 && val[i][k] == val[k][j]) {
                    dp[i][j] = 1;
                    val[i][j] = val[i][k] + 1;
                }
                else {
                    chmin(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
    }
    return dp[0][N];
}

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

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

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

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

Educational Codeforces Round 83 E. Array Shrinking (R2100)

問題概要

制約

考えたこと