字符串折叠

1090: [SCOI2003]字符串折叠

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

14

HINT

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

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>

using namespace std;

const int maxn=108;
typedef long long ll;
char str[maxn];
int dp[maxn][maxn],n;
bool check(int l,int r,int len){
    for(int i=1;i<=len;++i){
        for(int j=l+i-1;j+len<=r;j+=len){
            if(str[j]!=str[j+len])return false;
        }
    }
    return true;
}
int solve(int cur){
    if(cur<10)return 1;
    else if(cur<100)return 2;
    else if(cur<1000)return 3;
    else if(cur<10000)return 4;
}
int main(){
    //freopen("1.txt","r",stdin);
    scanf("%s",str+1);
    n=strlen(str+1);
    for(int i=n;i;--i){
        dp[i][i]=1;
        for(int j=i+1;j<=n;++j){
            dp[i][j]=j-i+1;
            for(int k=i;k<=j;++k){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
            for(int k=1;k<=j-i+1;++k){
                if((j-i+1)%k==0&&check(i,j,k)) {
                    dp[i][j] = min(dp[i][j], dp[i][i+k-1]+2+solve((j-i+1)/k));
                }
            }
            //cout<<dp[i][j]<<endl;
        }
    }
    printf("%d
",dp[1][n]);
    return 0;
}