题目描述
http://codeforces.com/gym/102835/problem/E
Solution
我们令 $f[l][r][o]$ 表示将区间 $[l,r]$ 都清空后颜色 $o$ 最多剩多少
另外在单独记录一下区间 $[l,r]$ 是否可以被全部清空
转移需要再枚举一个 $k$
时间复杂度 $O(n^3)$
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
| #include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <cstring>
#define maxn 510
using namespace std;
int id[256];
int n, m, L[maxn], R[maxn];
char s[maxn];
int f[maxn][maxn][8], g[maxn][maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
id['R'] = 1; id['G'] = 2; id['B'] = 3; id['C'] = 4; id['M'] = 5; id['Y'] = 6; id['K'] = 7;
cin >> s + 1 >> m; n = strlen(s + 1);
fill(f[0][0], f[0][0] + maxn * maxn * 8, -1);
for (int i = 1; i <= n; ++i)
L[i] = s[i] == s[i - 1] ? L[i - 1] : i;
for (int i = n; i; --i)
R[i] = s[i] == s[i + 1] ? R[i + 1] : i;
for (int l = 1; l <= n; ++l)
for (int i = 1, j = l; j <= n; ++i, ++j) {
if (R[i] >= j) f[i][j][id[s[i]]] = j - i + 1;
for (int o = 1; o <= 7; ++o)
for (int k = i; k < j; ++k) {
int u = -1, v = -1;
if (~f[i][k][o] || g[i][k]) u = max(0, f[i][k][o]);
if (~f[k + 1][j][o] || g[k + 1][j]) v = max(0, f[k + 1][j][o]);
if (~u && ~v) f[i][j][o] = max(f[i][j][o], u + v);
}
for (int o = 1; o <= 7; ++o) g[i][j] |= f[i][j][o] >= m;
}
cout << (g[1][n] ? "Yes" : "No") << "\n";
return 0;
}
|