bzxoj1090 字符串折叠

时间：2024-12-02 21:06:07

Description

折叠的定义如下： 1. 一个字符串可以看成它自身的折叠。记作S  S 2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S)  SSSS…S(X个S)。 3. 如果A  A’, BB’，则AB  A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B)  AAACBB，而2(3(A)C)2(B)AAACAAACBB 给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。

Input

仅一行，即字符串S，长度保证不超过100。

Output

仅一行，即最短的折叠长度。

区间dp，t[i][j]表示i开头长度为j的串的重复次数，f[i][j]表示i开头长度j的串的最短长度。

#include<cstdio>

#include<cstring>

char s[];

int f[][];

int t[][];

int v[];

inline void mins(int&a,int b){if(a>b)a=b;}

int main(){

    for(int i=;i<;i++)v[i]=;

    for(int i=;i<;i++)v[i]=;

    v[]=;

    scanf("%s",s);

    int l=strlen(s);

    for(int i=;i<=l;i++)

        for(int j=;j<=l;j++)f[i][j]=j;

    for(int i=;i<=l;i++){

        t[l-i][i]=;

        for(int j=i+;j<=l;j++){

            t[l-j][i]=;

            bool d=;

            for(int k=;k<i;k++){

                if(s[l-j+k]!=s[l-j+i+k]){

                    d=;

                    break;

                }

            }

            if(d)t[l-j][i]=t[l-j+i][i]+;

        }

    }

    for(int i=;i<=l;i++){

        for(int j=;j<=i;j++){

            if(i%j==){

                int c=i/j;

                for(int k=;k<l;k++)

                    if(t[k][c]>=j)mins(f[k][i],f[k][c]+v[j]);

            }

        }

        for(int k=;k<l;k++)

            for(int a=;a<i;a++)mins(f[k][i],f[k][a]+f[k+a][i-a]);

    }

    printf("%d",f[][l]);

    return ;

}

相关文章