题目描述

折叠的定义如下：

1. 一个字符串可以看成它自身的折叠。记作S = S
2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。

3. 如果A = A’, B = B’，则AB = A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B) = AAACBB，而2(3(A)C)2(B) = AAACAAACBB

   给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。

输入输出格式

输入格式：

仅一行，即字符串S，长度保证不超过100。

输出格式： 

仅一行，即最短的折叠长度。

 

输入输出样例

输入样例#1： 

NEERCYESYESYESNEERCYESYESYES

输出样例#1： 

14

说明

一个最短的折叠为：2(NEERC3(YES))

 

Solution

这道题属于很典型的区间DP.

状态定义:

f[ i ][ j ] 表示从i 到 j 的最小长度.

前导状态:

f [ i ][ j ] 初始化为原长 j - i +1.

f [ i ][ k ] 和 f[ k+1 ][ j ] 枚举断点并且更新.

如果要实现合并操作的话.

我们枚举的两个区间要满足几个条件:

1. 后面 的区间长度要整除前面合并的第一项长度 (因为合并都是从前面开始所以只需考虑后区间被前区间合并)

2. 后面的区间每一段都与其相同.

对于这个,我们直接暴力即可实现.

 

然后在 hzwer 学长那里学了一个高级的枚举. 无需担心区间边界问题 ! 递归实现 !

 

 

代码

#include
     
      using namespace std;char ch[101];int f[101][101];bool vich[101][101];bool judge(int l,int r,int cl,int cr){         if((r-l+1)%(cr-cl+1)!=0) return 0;         for(int i=l;i<=r;i++)         if(ch[i]!=ch[(i-l)%(cr-cl+1)+cl]) return 0;         return 1;}int cal(int x){
    int ans=0; while(x%10!=0){ans++;x/=10;}return ans;}//cal 为合并后数字的长度int ans(int l,int r){    if(vich[l][r])return f[l][r];     vich[l][r]=1;     f[l][r]=r-l+1;   //初始化为其长度.    for(int i=l;i