Codeforces Round #336 (Div. 1) B. Zuma

問題

codeforces.com

解法

まず少し観察します。
例えば 1 1 4 5 1 4 という数列を考えると, 例えば
1 1 4 5 1 4 -> 4 5 1 4 -> 4 1 4 -> 終わり
というようなものが考えられます。

これを考えると, 数列の部分数列(連続でなくて良い)の中でいかに上手く回文を作るかがキーになっているような気がします。
さっきのような回文の取り除き方をしたときには, "1 1", "5", "4 1 4" という 3 つの回文になる部分数列があったということになるわけです。
ただ, 部分数列になっているなら何でも良いわけではないです。例えば, 上の数列には "1 1 1", "4 5 4" という回文になっている 2 つの部分数列がありますが, これを採用することは出来ません。これは, "1 1 1" が [0, 4] 区間の間にあり, "4 5 4" が [2, 5] 区間の中にあり, ２つの区間が重なってしまっているからです。

これくらいのことを考えると, どう考えても区間 dp に落とし込めるような気がしてきます。

dp[l][r] = (区間 [l, r] の間にある回文の最小個数) とします。
すると, まず l==r の時は 1, l > r の時は 0 です。
あとは, c[l] == c[i] の時, [i, l] 間で回文を作ることを考えると, dp[l+1][i-1] と dp[i+1][r] を調べるようにすると, よくある回文の dp みたいになります。

下のコードではこれをメモ化再帰で実装しました。

まとめ

• 区間 DP まで思いついてたのに出来なかったのは, 「区間の中で上手い部分数列回文を探そう」とかいう意味不明なことをやろうとしていたため
  • 回文でよくある DP みたいにやることはなぜか思いつかなかった…次は絶対思いつくマンになるぞ
• 考えるベースとして 114514 シリーズは結構良い指標になる

const int MAXN = 555;
int c[MAXN];
int dp[MAXN][MAXN];

// [l, r]
int dfs(int l, int r) {
    int& ret = dp[l][r];
    if (ret >= 0) return ret;
    if (l>r) return ret = 0;
    if (l==r) return ret = 1;
    ret = dfs(l, l) + dfs(l+1, r);
    for (int i = l+1; i <= r; i++) {
        if (c[l] == c[i]) {
            if (i==l+1) ret = min(ret, 1+dfs(l+2, r));
            else ret = min(ret, dfs(l+1, i-1) + dfs(i+1, r));
        }
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, n-1) << endl;
    return 0;
}