P2400 秘密文件

    • 75通过
    • 242提交
  • 题目提供者 nonprocess
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 福建省历届夏令营
  • 难度 省选/NOI-
  • 时空限制 500ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    某天,情报局得到了一份秘密文件。文件的内容是加密后的全部由大写字母组成字符串。情报局局长小明想将其发送给远在东方神秘的xx大陆上的老朋友小刘来解密。然而若字符串太长,则需要很长的发送时间,太不安全了,因此小明想尽量将其缩短。于是小明制定了这样一个缩短规则:若一个字符串t连续出现k次,则可以用k(t)进行说明。如ABABAB可以缩成3(AB)。当然,重复缩短是允许的,如ABABABAAAAAAABABABAAAAAA可以缩成2(3(AB)6(A))

    现在,小明想知道,对于给定的字符串,最短可以缩成什么样子。

    注意:有多个最优方案时,输出其中字典序最小的。( thanks to @Dilute. )

    输入输出格式

    输入格式:

    输入仅一行,为给定的字符串。

    输出格式:

    输出仅一行,为经过缩短操作后的字符串。

    输入输出样例

    输入样例#1: 复制
    AAAAAAAAAABABABCCD
    输出样例#1: 复制
    9(A)3(AB)CCD

    说明

    【数据范围】

    对于l00%的数据,字符串的长度L≤100。数据存在一定梯度。

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