[SCOI2003]字符串折叠（区间dp）

P4302 [SCOI2003]字符串折叠

题目描述

折叠的定义如下：

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。

输入输出格式

输入格式：

仅一行，即字符串S，长度保证不超过100。

输出格式：

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

输入输出样例

输入样例#1：

NEERCYESYESYESNEERCYESYESYES

输出样例#1：

14

说明

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

考试的题目，还不会区间dp，什么都不知道，考试的时候思路大概想到了，但是没有想到怎么实现。

用\(F[i][j]\)表示从第\(i\)个字符到第\(j\)个字符的最小长度。枚举中间断点，一定要先处理完中间才能处理两边，考试的时候就是不晓得怎么枚举(我还是太菜了)。

还有一点很容易错的，字符折叠起来前面的数字可能为不止占一位(如AAAAAAAAAA ---> 10(A))。

难点在于怎样判断折叠，看到网上很多大佬用%什么的很麻烦，其实我们只要算出折叠完后字母部分有多长，然后用当前位置减去长度就可以了。因为既然可以枚举到这里，那么前面一定保证了相同，这是我们没必要一定搞到第一个的位置去判断。具体看代码吧

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

int len;

int f[110][110];

int dp[110];

char ch[110];

bool get(int x1,int y1,int x2,int y2)

{

    if((y2-x1+1)%(y1-x1+1)!=0) return false;

    int len=y1-x1+1;

    for(int i=x2;i<=y2;i++)

    {

        if(ch[i]!=ch[i-len])

        return false;

    }

    return true;

}

int cal(int k)

{

    int qwe=0;

    while(k)

    {

        qwe++;

        k/=10;

    }

    return qwe;

}

int main()

{

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

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

    memset(f,0x3f,sizeof(f));

    cin>>ch;

    len=strlen(ch);

    for(int i=0;i<len;i++)f[i][i]=1;

    for(int l=1;l<len;l++)

    {

        for(int i=0;i<len-l;i++)

        {

            int j=i+l;

            f[i][j]=(j-i+1);

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

            {

                if(!get(i,k,k+1,j))

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

                else f[i][j]=min(f[i][j],f[i][k]+2+cal((l+1)/(k-i+1)));

                //printf("f[%d][%d]=%d\n",i,j,f[i][j]);

            }

        }

    }

    cout<<f[0][len-1];

    return 0;

}