[SCOI2007]压缩

题意：
给与一个长度不超过50的字符串，它可以按下列方式压缩：

M是开始，R是重复从前一个M开始的字符串。
求字符串压缩后的最短长度。

思路：
区间dp:
dp[i][j][0/1]:dp[i][j][0]表示从i到j这段字符串中没有有M、dp[i][j][1]表示从i到j这段字符串中可以出现M的最少字符数。
当一段字符串可以被压缩时：
dp[i][j][0]=min(dp[i][j][0],dp[i][i+k/2-1][0]+1);(无M才可以被压缩)
字符串更新时：
dp[i][j][0]=min(dp[i][j][0],dp[i][x][0]+(j-x)(后一段的字符数))(x>=i&&x<=j)(合并成无M的字符串，前一段可以被压缩，而后一段一定没被压缩)
dp[i][j][1]=min(dp[i][j][1],dp[i][x][1]+dp[x+1][j][1]+1)(二段可以出现M的字符串合并时，中间需要加一个M间隔)
dp[i][j][1]=min(dp[i][j][1],dp[i][j][0]);(可以出现的情况分为出现和不出现)

代码：

#include <bits/stdc++.h>
#define inf 1000000007
#define eps 0.000001
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int dp[105][105][2];

int main()
{
    string s;
    cin >> s;
    int n=s.length();
    for(int k=1; k<=n; k++)
    {
        for(int l=0; l+k-1<n; l++)
        {
            int r=l+k-1;
            dp[l][r][0]=k;
            dp[l][r][1]=k;
            if(k%2==0)
            {
                int p=0;
                for(int i=l,j=l+k/2; i<l+k/2; i++,j++)
                {
                    if(s[i]==s[j])
                    {
                        ;
                    }
                    else
                    {
                        p=1;
                        break;
                    }
                }
                if(!p)
                {
                    dp[l][r][0]=min(dp[l][r][0],dp[l][l+k/2-1][0]+1);
                }
            }
            for(int x=l; x<=r; x++)
                dp[l][r][0]=min(dp[l][r][0],dp[l][x][0]+r-x);
            for(int x=l; x<=r; x++)
                dp[l][r][1]=min(dp[l][r][1],dp[l][x][1]+dp[x+1][r][1]+1);
            dp[l][r][1]=min(dp[l][r][1],dp[l][r][0]);
        }
    }
    printf("%d\n",dp[0][n-1][1]);
    return 0;
}