Typical DP Contest I

問題

iとwからなる文字列 $s$ に対して，以下の操作を最大で何回行えるか求めよ．

連続するiwiを $s$ から取り除く．

制約

$1 \leq |s| \leq 300$

考察

操作を後ろから考えると DP が立つ．

$i \lt j \lt k$ について $s_is_js_k = \text{iwi}$ が成り立つとき， $s_is_js_k$ を操作対象にするには，これらを隣接させないといけない，つまり $s_{(i, j)}, s_{(j, k)}$ が操作によって空文字列に変換できなければならない．

そこで $c_{i, j} =$ 「 $s_{[i, j]}$ が消せるか？」という値を求めることにする。これは以下のいずれかの場合のみ真となる。

$[i, j]$ が空集合
ある $i \lt k \lt j$ が存在して， $s_is_ks_j = \text{iwi}$ かつ $c_{i + 1, k - 1} \land c_{k + 1, j - 1}$
ある $i \leq k \lt j$ が存在して， $c_{i, k} \land c_{k + 1, j}$

$k$ は $O(n)$ 通りなので、 $c_{i, j}$ は $O(n^3)$ で求まる。

同様にして $dp_{i, j} =$ 「 $s_{[i, j]}$ に対する最大の操作回数」も以下の式で求まる。

$$ dp_{i, j} = \begin{cases} \frac{j - i + 1}{3} & (c_{i, j} = \top) \\ \max_{i \leq k \lt j} \{ dp_{i, k} + dp_{k + 1, j} \} & (c_{i, j} = \bot) \end{cases} $$ 計算量は $c_{i, j}$ と同様 $O(n^3)$ ．

実装例

提出 #9675043 - Typical DP Contest

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


#include <iostream>
#include <vector>
#include <string>

template <class T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }

void solve() {
    std::string s;
    std::cin >> s;
    int n = s.length();

    auto dp = vec(n, vec(n, 0));
    auto clean = vec(n, vec(n, false));
    for (int i = 1; i < n; ++i) {
        clean[i][i - 1] = true;
    }

    for (int l = 0; l < n; ++l) {
        for (int i = 0; i + l < n; ++i) {
            int j = i + l;

            // clean check
            // create iwi
            if (s[i] == 'i' && s[j] == 'i') {
                for (int k = i + 1; k <= j - 1; ++k) {
                    if (s[k] == 'w' &&
                        clean[i + 1][k - 1] && clean[k + 1][j - 1]) {
                        clean[i][j] = true;
                    }
                }
            }
            // separate
            for (int k = i; k + 1 <= j; ++k) {
                if (clean[i][k] && clean[k + 1][j]) clean[i][j] = true;
            }

            if (clean[i][j]) dp[i][j] = (l + 1) / 3;

            for (int k = i; k + 1 <= j; ++k) {
                dp[i][j] = std::max(dp[i][j], dp[i][k] + dp[k + 1][j]);
            }
        }
    }

    std::cout << dp[0][n - 1] << std::endl;
}