Typical DP Contest I問題 : イウィ

問題. イウィ

'i'と'w'からなる文字列sが与えられる．sの連続する部分文字列"iwi"を取り除く操作を繰り返す．操作を行うことのできる回数の最大値を求めよ．

制約：

解法. 区間DP

区間DPで解きます．解法は問題「ダルマ落とし」とほぼ同じです．異なるところは，「ダルマ落とし」では隣り合う2要素を取り除くという操作でしたが，この問題は隣り合う3要素となります．
区間を引数にとる関数を，
　 のときに取り除くことができる最大の文字数
として，下のソースコードのような漸化式をとり，部分文字列のサイズを小さい方から計算します．このとき， は取り除くことができる最大の文字数なので，答えの最大の操作回数は を3で割った値となります．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

int Solve(const int n, const string &s) {
    vector<vector<int>> dp(n, vector<int>(n));

    for (int i = 0; i + 3 <= n; ++i)
        if (s.substr(i, 3) == "iwi") dp[i][i + 2] = 3;

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

            if ((s.substr(l, 2) == "iw" && s[r] == 'i' && dp[l + 2][r - 1] == r - l - 2) ||
                (s.substr(r - 1, 2) == "wi" && s[l] == 'i' && dp[l + 1][r - 2] == r - l - 2)) {
                dp[l][r] = r - l + 1;
                continue;
            }

            for (int m = l; m < r; ++m)
                dp[l][r] = max(dp[l][r], dp[l][m] + dp[m + 1][r]);
        }
    }

    return dp[0][n - 1]  / 3;
}

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

    string s;

    cin >> s;
    cout << Solve(s.size(), s) << endl;

    return 0;
}

まとめ

区間DPは典型DPらしい．