P2470 [SCOI2007]压缩

    • 290通过
    • 541提交
  • 题目提供者 蔡伟斌
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 区间动规,区间dp 字符串 各省省选 四川
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给一个由小写字母组成的字符串,我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以(但不必)包含大写字母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: 复制
    aaaaaaa
    输出样例#1: 复制
    5
    输入样例#2: 复制
    bcdcdcdcdxcdcdcdcd
    输出样例#2: 复制
    12

    说明

    在第一个例子中,解为aaaRa,在第二个例子中,解为bMcdRRxMcdRR。

    【限制】

    50%的数据满足:1<=n<=20

    100%的数据满足:1<=n<=50

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。