BZOJ 1068

テーマリンク:http://61.187.179.132/JudgeOnline/problem.php?id=1068
文字列の圧縮.Mは反復列の開始を表し、Rは前のMとの間の重複を表す.一番短い列を圧縮します.
考え:f[i][j][0]はまだMがなくて、f[i][j][1]はすでにMがあります.
 

char s[N];





int ok(int L,int R)

{

    int M=(R-L+1)>>1;

    int i;

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

    return 1;

}





int f[N][N][2];





int DFS(int L,int R,int t)

{

    if(f[L][R][t]!=-1) return f[L][R][t];

    if(L==R) return f[L][R][t]=1;

    int x=R-L+1,len=x;

    int i;

    if(t)

    {

        for(i=L;i<R;i++) upMin(x,DFS(L,i,1)+1+DFS(i+1,R,1));

    }

    for(i=L;i<R;i++) upMin(x,DFS(L,i,t)+R-i);

    if(len%2==0&&ok(L,R)) upMin(x,DFS(L,L+len/2-1,0)+1);

    return f[L][R][t]=x;

}





int n;





int main()

{

    RD(s); n=strlen(s);

    clr(f,-1);

    PR(DFS(0,n-1,1));

}