【bzoj1068】[SCOI2007]压缩

2015.05.28 19:59 Thu | 15次阅读 | 旧日oi | 固定链接 | 源码

题目大意:自己看去吧……
题解
很显然这是一道区间dp,但是需要注意的地方非常多……题解写代码里了

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 0x3f3f3f3f
using namespace std;
char s[55];
int f[55][55][2],n;
bool same(int l,int r)
{
    if((r-l+1)&1) return 0;
    int mid=(r-l+1)/2;
    for(int i=l;i<l+mid;i++) if(s[i]!=s[i+mid]) return 0;
    return 1;
}
int dp(int l,int r,int t)//从l到r,放不放M的方案数 
{
    if(l==r) return 1;
    if(f[l][r][t]) return f[l][r][t];
    int tmp=inf;
    if(t==1) for(int i=l;i<r;i++) tmp=min(tmp,1+dp(l,i,1)+dp(i+1,r,1));
    //如果左边放M,要压缩右面的话必须在中间加一个M 
    for(int i=l;i<r;i++) tmp=min(tmp,dp(l,i,t)+r-i);//不压缩右面就不用放了 
    if(same(l,r)) tmp=min(tmp,dp(l,(l+r)/2,0)+1);//如果左右完全一样,在左面不放M的情况下可以把右面用一个R代替
    return f[l][r][t]=tmp;
}
int main()
{
    //freopen("compress.in","r",stdin);
    //freopen("compress.out","w",stdout);
    scanf("%s",s+1);n=strlen(s+1);
    cout<<dp(1,n,1);
}```