首页 > 代码库 > BZOJ 1090 字符串折叠（区间DP）

BZOJ 1090 字符串折叠（区间DP）

2024-07-08 23:53:04   215人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1090

题意：字符串AAAAAAAAAABABABCCD的最短折叠为9(A)3(AB)CCD，注意数字的长度和圆括号都算最后长度。求一种折叠方式使得总长度最小。

思路：f[L][R]=min(R-L+1,f[L][i]+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));}

 

 

 


联系
我们