BZOJ1090: [SCOI2003]字符串折叠

区间dp.

一种是分段dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);

一种是这一段可以缩写dp[i][j]=min(dp[i][j],dp[i][l]+2+calc((j-i+1)/(l-i+1)));

calc表示计算十进制的位数

边界就是l==r f[l][r]=1

 #include<bits/stdc++.h>

 using namespace std;

 int read(){

   int x=,f=;char ch=getchar();

   while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

   while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

   return x*f;

 }

 char s[];

 int f[][];

 #define inf 1e9

 bool judge(int l,int k,int r){

   int tmp=;

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

     if(s[l+tmp]!=s[i])return ;

     tmp=tmp+%(k-l+);

   }

   return ;

 }

 int calc(int x){

   int tmp=;

   while(x){

     tmp++;x/=;

   }

   return tmp;

 }

 int dp(int l,int r){

   if(l==r)return ;

   if(f[l][r])return f[l][r];

   int t=r-l+;

   for(int k=l;k<r;k++)t=min(t,dp(l,k)+dp(k+,r));

   for(int k=l;k<r;k++)if((r-l+)%(k-l+)==&&judge(l,k,r))t=min(t,+dp(l,k)+calc((r-l+)/(k-l+)));

   return f[l][r]=t;

 }

 int main(){

   scanf("%s",s);

   int l=strlen(s);

   printf("%d\n",dp(,l-));

   return ;

 }

1090: [SCOI2003]字符串折叠

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1046 Solved: 680
[Submit][Status][Discuss]

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

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

Sample Input

NEERCYESYESYESNEERCYESYESYES

Sample Output

HINT

一个最短的折叠为：2(NEERC3(YES))

秒客网