题目描述

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

输入描述:

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

输出描述:

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

题解

由于每次压缩的都是连续的一段，就像一个个小区间一样，所以考虑区间DP。

比较容易想到的是表示字符串的第l个字符到第r个字符的最短压缩长度。

第1种转移，就是

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

但上面的分析是错的。因为我们并没有考虑M字符对于串的影响。也就是说转移会受到子串区间[l,mid]的中M的限制。因为R是在匹配离他最近的M，并不是从我们区间开头开始匹配。

那么如何解决这个问题呢？我们可以多加一维限制，设置状态为

表示子串[l,r]区间中存在M字符；

表示子串[l,r]区间不存在M字串。

第1种转移为

第2种转移为，即枚举M所在的位置

第3种转移也就是子串[l,r]可以拆分成两个相等的子串[l,mid]和、[mid+1,r]的情况。此时转移：，这样就解决了M的影响。

最后答案就是。

code

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=2e5+100;
int dp[60][60][2];
string s;
bool check(int l,int r){
    int mid=(l+r)>>1;
    for(int i=l;i<=mid;++i){
        if(s[i]!=s[mid+i-l+1])return false;
    }
    return true;
}
////////////////////////////////////////////////////////////////////////
int main(){
    cin>>s;
    int n=s.length();
    s="#"+s;
    for(int len=1;len<=n;++len){
        for(int i=1;i+len-1<=n;++i){
            int j=i+len-1;
            dp[i][j][0]=dp[i][j][1]=len;
            for (int k=i;k<=j;++k){
                dp[i][j][0]=min(dp[i][j][0],dp[i][k][0]+j-k);
                dp[i][j][1]=min(dp[i][j][1],min(dp[i][k][1],dp[i][k][0])+min(dp[k+1][j][0],dp[k+1][j][1])+1);
            }
            if(len%2==0&&check(i,j))dp[i][j][0]=min(dp[i][j][0],dp[i][(i+j)>>1][0]+1);
        }
    }
    print(min(dp[1][n][0],dp[1][n][1])),putchar(10);
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/