题目描述

给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。 压缩后的字符串除了小 写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没 有M，则从串的开始算起）开始的解压结果（称为缓冲串）。 bcdcdcdcd可以压缩为bMcdRR，另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。

输入描述

输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。

输出描述

输出仅一行，即压缩后字符串的最短长度。

解析

首先这个题目中，要压缩便是压缩重复的部分，就是一个个小的区间之间进行压缩，我们要求缩小的的最小长度，我们就要考虑怎么将最多的区间压缩，自然我们就考虑使用区间dp

如果不考虑这个M的，直接用R表示重复的字符串，那么这个题目就很容易解决了，很容易我们就考虑使用表示第l个字符到第r个字符的最短压缩长度.

第一种转移这个并不难理解，就是在这个区间中找到尽可能多的重复的串，然后用R表示出来就能压缩成最短的的长度。

第二种转移就是子串长度为偶数，并且可以拆分成两个相等的子串时的转移，即此时可以压缩。设,所以就有

但是这里我们还要考虑M，那么我们的处理就可以改成再加一维，用表示在区间之间是否存在M，如果存在即为否则就是,

第一种转移即为

第二种转移为，这里就是在枚举M的位置。

第三种就是将和上面不考虑M的第二种一样,,

最后的答案就是.

代码

#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#define ll long long
using namespace std;
int n,m;
int dp[1005][1005][2];
string s;
int judge(int l,int r){
    int mid=(l+r)/2;
    for(int i=l;i<=mid;++i)
        if(s[i]!=s[mid+1+i-l])
            return 0;
    return 1;
}
int main (void){
    int T,i,t,j,k,p,sum=0;
    cin>>s;
    int len=s.length();
    dp[0][0][0]=1;
    for(int i=1;i<=len;++i){
        for(int l=0;l<len-i+1;++l){
            int r=l+i-1;
            dp[l][r][0]=i;dp[l][r][1]=i;
            for(int j=l;j<=r;++j){
                dp[l][r][0]=min(dp[l][j][0]+r-j,dp[l][r][0]);
                dp[l][r][1]=min(dp[l][r][1],min(dp[l][j][1],dp[l][j][0])+1+min(dp[j+1][r][1],dp[j+1][r][0]));
            }
            if(i%2==0 && judge(l,r) )
                dp[l][r][0]=min(dp[l][r][0],dp[l][(l+r)/2][0]+1);
        }
    }
    p=min(dp[0][len-1][0],dp[0][len-1][1]);
    cout<<p<<endl;
    return 0;
}