Typical DP Contest I - イウィ
kmjpさんの解説を見ました。
solution
区間$[l,r)$が取り除けるかそれぞれ調べ、これを元に区間$[l,n)$で取り除ける数を数える。$O(N^3)$。
区間$[l,r)$が取り除けるのは、
- $l = r$のとき
- ある$m \in [l,r)$があって、
- $s_l = \operatorname{i}, s_m = \operatorname{w}, s_{r-1} = \operatorname{i}$であり、区間$[l+1,m-1]$と区間$[m+1,r-1]$が取り除けるとき
- 区間$[l,m)$と区間$[m,r)$が取り除けるとき
これを、区間の長さ$r-l$の小さい順に更新していけばよい。
implementation
#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;
template <class T> bool setmax(T & l, T const & r) { if (not (l < r)) return false; l = r; return true; }
template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); }
template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors(a, y, zs...); return vector<decltype(cont)>(x, cont); }
int main() {
string s; cin >> s;
int n = s.length();
vector<vector<bool> > removable = vectors(false, n+1, n+1); // [l, r)
repeat (l,n) removable[l][l] = true;
repeat_from (len,3,n+1) {
repeat (l,n) {
int r = l+len;
if (n < r) break;
repeat_from (m,l,r+1) {
if (s[l] == 'i' and s[m] == 'w' and s[r-1] == 'i'
and removable[l+1][m]
and removable[m+1][r-1]) {
removable[l][r] = true; // remove a new iwi
break;
}
if (removable[l][m] and removable[m][r]) {
removable[l][r] = true; // merge two removables
break;
}
}
}
}
vector<int> dp(n+1); // [l, n)
repeat_reverse (l,n) {
dp[l] = dp[l+1];
repeat_from (r,l,n+1) if (removable[l][r]) {
setmax(dp[l], r-l + dp[r]);
}
}
cout << dp[0] / 3 << endl;
return 0;
}