给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小
写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没
有M，则从串的开始算起）开始的解压结果（称为缓冲串）。 bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程
另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。
| 题目名称 | 2409. [SCOI 2007]压缩 |
|---|---|
| 输入输出 | compress.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 MistyEye
于2016-08-01加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：67， 提交：130， 通过率：51.54% | ||||
 AntiLeaf |
100 | 0.000 s | 0.00 MiB | C++ |
 槿柒 |
100 | 0.000 s | 0.00 MiB | C++ |
 HZOI_蒟蒻一只 |
100 | 0.000 s | 0.00 MiB | C++ |
 Samle |
100 | 0.000 s | 0.00 MiB | C++ |
 Youngsc |
100 | 0.000 s | 0.00 MiB | C++ |
 lihaoze |
100 | 0.000 s | 0.00 MiB | C++ |
 Hzoi_ |
100 | 0.002 s | 0.30 MiB | C++ |
 NewBee |
100 | 0.002 s | 0.30 MiB | C++ |
 Hzoi_moyi |
100 | 0.002 s | 0.32 MiB | C++ |
 Hallmeow |
100 | 0.002 s | 0.34 MiB | C++ |
| 关于 压缩 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
 Hzoi_Mafia
2017-06-10 18:48
12楼
| ||||
|
回复 @Hallmeow :
用的头像还得以为你是女的。。。  Hzoi_QTY
2017-06-10 18:39
11楼
| ||||
|
VIP我™竟然打了两个stdout~~~~(>_<)~~~~
| ||||
|
HZOI_蒟蒻一只
2017-06-10 17:23
9楼
| ||||
|
Hzoi_Mafia
2017-06-10 16:42
8楼
| ||||
|
HZOI_蒟蒻一只
2017-06-10 16:38
7楼
| ||||
|
榜上最后一名= =
我预测10分钟后我就下去了= = Hzoi_Mafia
2017-06-10 15:59
6楼
| ||||
|
两百题斩！
槿柒
2016-08-07 19:45
5楼
| ||||
|
| ||||
|
另一种DP，效率貌似更高一些
| ||||
【题目描述】
【输入格式】
输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。
【输出格式】
输出仅一行，即压缩后字符串的最短长度。
【样例输入】
bcdcdcdcdxcdcdcdcd
【样例输出】
12
【提示】
在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。
【限制】
100%的数据满足：1<=n<=50 100%的数据满足：1<=n<=50