BZOJ1090：[SCOI2003]字符串折叠——题解

http://www.lydsy.com/JudgeOnline/problem.php?id=1090

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

14

——————————————————————————————————

我竟然自己做了一道dp！

f[i][j]表示i～j压缩后最短长度。

显然我们有：

for(int k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);

接下来就是压缩了。

我们可以枚举区间长度的倍数，然后判断是否可以压缩，并且判断压缩之后是否会变的更小即可了！

复杂度看似O(n^3*根号n)，但是实际上达不到，所以能过就是了。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=110;
int f[N][N];
char s[N];
inline int w(int x){
    if(x==100)return 5;
    if(x>=10)return 4;
    return 3;
}
bool check(int k,int l,int r,int len){
    for(int i=l+len;i<=r;i++){
    if(s[i-len]!=s[i])return 0;
    }
    return 1;
}
int main(){
    cin>>s+1;
    int n=strlen(s+1);
    for(int i=1;i<=n;i++)f[i][i]=1;
    for(int l=2;l<=n;l++){
    for(int i=1;i<=n-l+1;i++){
        int j=i+l-1;
        f[i][j]=l;
        for(int k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
        for(int k=l;k>=1;k--){
        if(l%k)continue;
        int len=(j-i+1)/k;
        if(check(k,i,j,len)){
            if(f[i][j]>f[i][i+len-1]+w(k)){
            f[i][j]=f[i][i+len-1]+w(k);
            break;
            }
        }
        }
    }
    }
    printf("%d
",f[1][n]);
    return 0;
}