P2470 [SCOI2007]压缩

区间dp，记\(dp(l,r,t)\)表示区间\((l,r)\)，\(t\)表示这个区间中能不能放\(M\)。如果可以，枚举中间哪里放\(M\)来压缩。也可以不压缩，后面直接跟上去。如果左右重复的，尝试压缩一下，那么循环节里是不能放的

//minamoto

#include<bits/stdc++.h>

using namespace std;

const int N=55,inf=0x3f3f3f3f;

char s[N];int f[N][N][2],n;

bool same(int L,int R){

    if((R-L+1)&1)return false;int M=(R-L+1)>>1;

    for(int i=L;i<L+M;++i)if(s[i]!=s[i+M])return false;return true;

}

int solve(int L,int R,bool is){

    if(L==R)return 1;if(f[L][R][is])return f[L][R][is];int res=inf;

    if(is)for(int i=L;i<R;++i)res=min(res,1+solve(L,i,1)+solve(i+1,R,1));

    for(int i=L;i<R;++i)res=min(res,solve(L,i,is)+R-i);

    if(same(L,R))res=min(res,solve(L,(L+R)>>1,0)+1);return f[L][R][is]=res;

}

int main(){

//	freopen("testdata.in","r",stdin);

    scanf("%s",s+1);n=strlen(s+1);

    printf("%d\n",solve(1,n,1));return 0;

}

巴特西

P2470 [SCOI2007]压缩

最新文章

热门文章