BZOJ 1090文字列折りたたみ(区間DP)
1354 ワード
テーマリンク:http://61.187.179.132/JudgeOnline/problem.php?id=1090
文字列A A A AAA ABABABABCCDの最短折りたたみは9(A)3(AB)CCDで、数字の長さと丸括弧が最後の長さとなるように注意してください.折りたたみ式を求めると、全体の長さが最小になります.
考え方:f[L][R]=min(R-L+1,f[L]+f[i+1][R])、また[L,R]を[i+1,R]で何回か繰り返すことができれば、折り畳み後の長さ更新f[L][R]も利用できる.
文字列A A A AAA ABABABABCCDの最短折りたたみは9(A)3(AB)CCDで、数字の長さと丸括弧が最後の長さとなるように注意してください.折りたたみ式を求めると、全体の長さが最小になります.
考え方:f[L][R]=min(R-L+1,f[L]+f[i+1][R])、また[L,R]を[i+1,R]で何回か繰り返すことができれば、折り畳み後の長さ更新f[L][R]も利用できる.
char s[N];
int f[N][N],n;
int OK(int a,int b,int c,int d)
{
int x=b-a+1;
int y=d-c+1;
if(x%y) return 0;
int i,j,k;
for(i=1;i<=x/y;i++)
{
for(j=(i-1)*y+1,k=c;j<=i*y;j++,k++)
{
if(s[j+a-1]!=s[k]) return 0;
}
}
return 1;
}
int cal(int x)
{
if(x<10) return 1;
if(x>=10&&x<=99) return 2;
return 3;
}
int DFS(int L,int R)
{
if(L==R) return 1;
if(f[L][R]!=-1) return f[L][R];
f[L][R]=R-L+1;
int i;
for(i=L;i<R;i++)
{
f[L][R]=min(f[L][R],DFS(L,i)+DFS(i+1,R));
}
for(i=L;i<R;i++) if(OK(L,i,i+1,R))
{
int x=R-L+1;
int y=R-i;
int t=cal(x/y);
f[L][R]=min(f[L][R],t+2+DFS(i+1,R));
}
return f[L][R];
}
int main()
{
RD(s+1); n=strlen(s+1); clr(f,-1);
PR(DFS(1,n));
}