bzoj 1090[SCOI 2003]文字列折り畳み

4562 ワード

Description
折りたたみの定義は次のとおりです.1.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)C 2(B)AAACBB、2(3(A)C)2(B)AAACBBは文字列を与え、その最短折りたたみを求める.例えばAAAAAAAAAAAABABCCDの最短折りたたみは、9(A)3(AB)CCDである.
Input
1行のみ、すなわち文字列Sであり、長さは100を超えないことを保証する.
Output
1行のみ、つまり最も短い折りたたみ長さです.
Sample Input
NEERCYESYESYESNEERCYESYESYES
Sample Output 14
HINTの最短折りたたみは2(NEERC 3(YES))です.
#include
#include
#include
#include
#define ll long long
using namespace std;
char a[105]; 
int p[105],f[105][105]; 
int n; 
int dp(int l,int r)
{

    if(l==r) return 1;
    if(f[l][r]!=-1) return f[l][r];
    int x=r-l+1; 
    for(int i=l;iint k=i-l+1,w=l+k,can=1;
        if((r-l+1)%k>0) continue;//     
        if(w>r) continue;
        while(1) 
        {
            for(int j=0;jif(a[l+j]!=a[w+j]) can=0;
            w=w+k;
            if(w>r) break; 
        }
        if(can) 
        {
            x=min(x,2+k+p[(r-l+1)/k]); //        
            for(int j=l;j1;j++)  //       
            x=min(x,2+dp(l,j)+dp(j+1,l+k-1)+p[(r-l+1)/k]); 
        }
    }
    for(int i=l;i1,r)); //     
    return f[l][r]=x; 
}
int main()
{
    for(int i=1;i<=9;i++) p[i]=1;
    for(int i=10;i<=99;i++) p[i]=2;
    p[100]=3; 
    scanf("%s",a+1);
    n=strlen(a+1); 
    memset(f,-1,sizeof(f));
    cout<1,n)<return 0;
}