BZOJ 1090: [SCOI2003]字符串折叠区间DP

2022-12-02 07:44:24

1090: [SCOI2003]字符串折叠

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

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

HINT

题意

题解：

哎呦卧槽，这道题和http://www.cnblogs.com/qscqesze/p/4782156.html这道题一模一样……

双倍经验爽呀！

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <bitset>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 110000

#define mod 10007

#define eps 1e-9

#define pi 3.1415926

int Num;

//const int inf=0x7fffffff;   //§ß§é§à§é¨f§³

const ll Inf=0x3f3f3f3f3f3f3f3fll;

inline ll read()

{

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

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

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

    return x*f;

}

//**************************************************************************************

string s[][];

int n;

int dp[][];

int vis[][];

char S[];

int FF(int x)

{

    int add=;

    while(x)

    {

        add++;

        x/=;

    }

    return add;

}

string F(int x)

{

    string ss;

    while(x)

    {

        ss+=(char)(x%+'');

        x/=;

    }

    reverse(ss.begin(),ss.end());

    return ss;

}

int solve(int l,int r)

{

    if(vis[l][r])return dp[l][r];

    vis[l][r]=;

    for(int i=l;i<r;i++)

    {

        if(dp[l][r]>solve(l,i)+solve(i+,r))

        {

            dp[l][r]=dp[l][i]+dp[i+][r];

            s[l][r]=s[l][i]+s[i+][r];

        }

    }

    for(int i=;i<r-l+;i++)

    {

        if((r-l+)%(i)!=)

            continue;

        int add = ;

        for(int k=;;k++)

        {

            if((k+)*i>r-l+)

                break;

            for(int j=;j<i;j++)

            {

                if(S[l+k*i+j]!=S[l+j])

                    break;

                if(j==i-)

                    add+=;

            }

        }

        if(add==(r-l+)/i)

        {

            int point=solve(l,l+i-)++FF(add);

            if(dp[l][r]>point)

            {

                dp[l][r]=point;

                s[l][r]="";

                s[l][r]+=F(add)+'(';

                s[l][r]+=s[l][()*i-+l];

                s[l][r]+=')';

            }

        }

    }

    return dp[l][r];

}

int main()

{

    scanf("%s",S+);

    n = strlen(S+);

    for(int i=;i<=n;i++)

    {

        for(int j=i;j<=n;j++)

        {

            dp[i][j]=j-i+;

            for(int k=;k<j-i+;k++)

            {

                s[i][j]+=S[i+k];

            }

        }

    }

    solve(,n);

    cout<<dp[][n]<<endl;

    return ;

}

码农公寓