Typical DP Contest I - イウィ

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi

解法

dp[l][r] := [l, r) で最大何文字取り除けるか
と定義する．
まず，dp[l][r] = max(dp[l][i] + dp[i][r]) (i = l, ..., r) という遷移は，明らかだと思う．
あとは，s[l...r) が完全に取り除ける（つまり dp[l][r] == r - l）場合，そこから端に "iwi" をくっつけられるか，を確認する．
例えば "iiwiwi" なら s[1...4) が "iwi" で，端に "i" + "wi" をくっつけられる．
iwi は 3 文字なので，くっつけられるかは普通に全部調べたらいい．

2020/01/13 追記
他のブログで参照されたときに読んで気がついたんですが，考慮するケースを1つ忘れています．具体的には "i" + s1 + "w" + s2 + "i" で s1, s2 が全部消せるやつ．
~~気が向いたときに直します（直すまでは以下のコードを参考にしないように）．~~

直しました．
あとこういう問題はメモ化再帰で書くとバグりにくいのでそっち版に書き直しました．
メモ化再帰のデメリットは for で書くより遅いことですね．

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s; cin >> s;
    const int n = s.size();

    vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
    function<int(int, int)> rec = [&] (int l, int r) {
        if(r - l <= 2) return 0;
        if(dp[l][r] != -1) return dp[l][r];

        int& res = dp[l][r];
        for(int m = l + 1; m < r; ++m) {
            res = max(res, rec(l, m) + rec(m, r));
            if(s[l] == 'i' && s[m] == 'w' && s[r - 1] == 'i') {
                if(rec(l + 1, m) == m - l - 1 && rec(m + 1, r - 1) == r - m - 2) {
                    res = r - l;
                }
            }
        }
        return res;
    };

    cout << rec(0, n) / 3 << endl;
}

感想

以下は全く同じ問題なので練習にどうぞ．
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1611&lang=jp