string stringbuffer stringbuild，BZOJ 1090: [SCOI2003]字符串折疊

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1916 Solved: 1257
[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

string stringbuffer stringbuild、僅一行，即最短的折疊長度。

Sample Input

NEERCYESYESYESNEERCYESYESYES
Sample Output

14
HINT

一個最短的折疊為：2(NEERC3(YES))

題解

區間dp，dp[i][j]表示區間[i,j]合并后的最小值。枚舉時要先判斷是否有可合并的串。

代碼

#include<bits/stdc++.h>using namespace std;
const int MAXN = 105;char c[MAXN];
int dp[MAXN][MAXN],leen;inline bool judge(int x,int y,int z){for(int i=1;i<=leen;i++)for(int j=x+i-1;j+z<=y;j+=z)if(c[j]!=c[j+z]) return false;return true;
}inline int cal(int k){if(k==100) return 3;if(k/10!=0) return 2;return 1;
}int main(){scanf("%s",c+1);memset(dp,0x3f,sizeof(dp));leen=strlen(c+1);for(int i=0;i<=leen;i++)dp[i][i]=1;for(int l=0;l<=leen;l++)for(int i=1;i<=leen-l;i++){int j=i+l;for(int k=1;k<=(l+1)>>1;k++){    //枚舉重復串的長度并判斷是否合法。 if(judge(i,j,k) and (l+1)%k==0)dp[i][j]=min(dp[i][j],dp[i][k+i-1]+2+cal((l+1)/k)) ;}for(int k=i;k<j;k++)   //枚舉中間位置。 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);}
//  for(register int i=1;i<=leen;i++)
//      for(register int j=1;j<=leen;j++)
//          cout<<dp[i][j]<<" ";cout<<dp[1][leen];return 0;
}