bzoj 1090[SCOI 2003]文字列折り畳み
4562 ワード
Description
折りたたみの定義は次のとおりです.1.1つの文字列は、それ自体の折りたたみと見なすことができます.SS 2と記す.X(S)は、X(X>1)個のSが接続された列の折りたたみである.X(S)SSSS...S(X個S)と記す.3.AA’,BB’の場合、ABA’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))です.
折りたたみの定義は次のとおりです.1.1つの文字列は、それ自体の折りたたみと見なすことができます.SS 2と記す.X(S)は、X(X>1)個のSが接続された列の折りたたみである.X(S)SSSS...S(X個S)と記す.3.AA’,BB’の場合、ABA’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;
}