给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小
写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没
有M，则从串的开始算起）开始的解压结果（称为缓冲串）。 bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程
另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。
| 题目名称 | 2409. [SCOI 2007]压缩 |
|---|---|
| 输入输出 | compress.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 MistyEy
于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++ |
|
野 |
100 | 0.000 s | 0.00 MiB | C++ |
|
李昊泽 |
100 | 0.000 s | 0.00 MiB | C++ |
|
hzoier |
100 | 0.002 s | 0.30 MiB | C++ |
|
LSY |
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