P2470-[SCOI2007]压缩
题目:
题目描述:
给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。
bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程：
| 已经解压的部分 | 解压结果 | 缓冲串 |
|---|
| b | b | b |
| bM | b | . |
| bMc | bc | c |
| bMcd | bcd | cd |
| bMcdR | bcdcd | cdcd |
| bMcdRR | bcdcdcdcd | cdcdcdcd |
输入格式:
输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。
输出格式:
输出仅一行，即压缩后字符串的最短长度。
样例:
样例输入1:
样例输出1:
样例输入2:
样例输出2:
思路:
首先我们有一个很直接的区间dp的思想: 记$f_{l, r}$表示将$l\to r$合并的最短长度, 然后枚举k转移, 但这显然是不对的比如 xababxabab 会压缩为 Mx(MabR)R 但必须和最右边的 R 匹配.
所以我们尝试多记一维$0/1$表示这个区间除了开头有没有其他的$M$, 再进行转移即可
实现:
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
48
49
50
51
52
53
54
55
56
57
58
59
60
| // Problem: P2470 [SCOI2007]压缩
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2470
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/ios.h"
int n;
string s;
const int maxn = 1010;
int opt[maxn][maxn][2];
int dfs(int l, int r, int d)
{
if (opt[l][r][d] != 0x3f3f3f3f)
return opt[l][r][d];
if (l == r)
return 2;
int &ans = opt[l][r][d];
if (d)
{
ans = r - l + 2;
bool flg = 1;
int mid = l + r >> 1;
if (!(r - l & 1))
flg = 0;
for (int i = l; i <= mid; i++)
if (s[i - 1] != s[i - l + mid])
flg = 0;
if (flg)
ans = min(ans, dfs(l, mid, 1) + 1);
for (int i = l; i < r; i++)
{
ans = min(ans, dfs(l, i, 1) + r - i);
}
}
else
{
for (int i = l; i < r; i++)
{
int dx = dfs(l, i, 0), dy = dfs(i + 1, r, 0);
if (i > l)
dx = min(dx, dfs(l, i, 1));
if (i + 1 < r)
dy = min(dy, dfs(i + 1, r, 1));
ans = min(ans, dx + dy);
}
}
return ans;
}
int main()
{
yin >> s;
n = s.size();
memset(opt, 0x3f3f3f3f, sizeof(opt));
yout << min(dfs(1, n, 0), dfs(1, n, 1)) - 1 << endl;
return 0;
}
|