[SCOI2007]压缩 题解

[SCOI2007]压缩 题解
很显然是一个dp。。。很妙的一个dp,很难的一个dp。。。
因为M，R存在造成的不同结果，需要分类讨论。
记:

1. dp[i][j][0]为区间[i,j]不加M时最短长度
2. dp[i][j][1]为区间[i,j]有M时最短长度

那么转移方程为：
dp[i][j][0]=min(dp[i][k][0]+i-k)| i<=k<=j
dp[i][j][0]=min(dp[i][j][0],dp[i][(i+j)/2][0]+1)|如果可以被压缩的话
dp[i][j][1]=min(min(dp[i][k][0],dp[i][k][1])+1+min(dp[k+1][j][0],dp[k+1][j][1])) | 枚举加入的M的位置

这个区间dp的精髓大约就是划分吧

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N=1e5+20;
const int INF=0x3f3f3f3f;
int dp[55][55][2];
char s[55];
int n;
bool fun(int l,int r){
    int len=r-l+1;
    if(len%2==1)return 0;
    int mid=(l+r)/2;
    for(int i=l,j=mid+1;i<=mid;i++,j++){
        if(s[i]!=s[j])return 0;
    }
    return 1;
}
int main(){
    //freopen("1.in","r",stdin);
    //freopen("square.out","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=0;i<55;i++){
        for(int j=0;j<55;j++){
            dp[i][j][0]=dp[i][j][1]=INF;
        }
    }
    for(int i=1;i<=n;i++)dp[i][i][0]=1,dp[i][i][1]=2;

    for(int len=2;len<=n;len++){
        for(int i=1;i<=n;i++){
            int l=i,r=i+len-1;
            if(r>n)continue;
            for(int k=l;k<=r;k++){
                dp[l][r][0]=min(dp[l][r][0],dp[l][k][0]+r-k);
            }
            if(fun(l,r)){
                dp[l][r][0]=min(dp[l][r][0],dp[l][(l+r)/2][0]+1);
            }
            for(int k=l;k<r;k++){
                dp[l][r][1]=min(dp[l][r][1],min(dp[l][k][0],dp[l][k][1])+1+min(dp[k+1][r][1],dp[k+1][r][0]));
            }
        }
    }
    int ans=min(dp[1][n][0],dp[1][n][1]);
    printf("%d\n",ans);
}