B1090 [SCOI2003]字符串折叠 区间dp

又一道区间dp，和上一篇类似，但是比他简单，这个只有两种转移方法，不是很复杂。直接判断是否为重复的串就行。

题干：

Description

折叠的定义如下： . 一个字符串可以看成它自身的折叠。记作S  S . X(S)是X(X>)个S连接在一起的串的折叠。记作X(S)  SSSS…S(X个S)。 . 如果A  A’, BB’，则AB  A’B’ 例如，因为3(A) = AAA, (B) = BB，所以3(A)C2(B)  AAACBB，而2((A)C)(B)AAACAAACBB 给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：(A)(AB)CCD。

Input

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

Output

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

Sample Input

NEERCYESYESYESNEERCYESYESYES

Sample Output

HINT

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

Source

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

#define duke(i,a,n) for(int i = a;i <= n;i++)

#define lv(i,a,n) for(int i = a;i >= n;i--)

#define clean(a) memset(a,0,sizeof(a))

const int INF =  << ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

char s[];

int f[][],n,l;

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

{

    if((y2 - x1 + ) % (y1 - x1 + ) != )

    return false;

    int len = y1 - x1 + ;

    duke(i,x2,y2)

    {

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

        return false;

    }

    return true;

}

int cal(int k)

{

    int cnt = ;

    while(k)

    {

        cnt++;

        k /= ;

    }

    return cnt;

}

int main()

{

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

    scanf("%s",s + );

    n = strlen(s + );

    duke(i,,n)

    f[i][i] = ;

    duke(l,,n - )

    {

        duke(i,,n - )

        {

            int j = i + l;

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

            duke(k,i,j - )

            {

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

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

                else

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

            }

        }

    }

    printf("%d\n",f[][n]);

    return ;

}