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