bzoj1090 [SCOI2003]字符串折叠——区间DP

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1090

区间DP...

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,ans,dp[][];

char c[];

bool pd(int l1,int r1,int l2,int r2)

{

    int k1=r1-l1+,k2=r2-l2+;

    if(k1%k2)return ;//前一个区间较长

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

        if(c[l1+i]!=c[l2+i%k2])return ;

    return ;

}

int cal(int x)

{

    int ret=;

    while(x)ret++,x/=;

    return ret;

}

int main()

{

    cin>>c;

    n=strlen(c);

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

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

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

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

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

        {

            int r=l+len;

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

            {

                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+][r]);

                if(pd(k+,r,l,k))dp[l][r]=min(dp[l][r],dp[l][k]++cal((r-k)/(k-l+)+));//纯折叠 //以l~k为一个循环节，注意不要除反了

            }

        }

    printf("%d",dp[][n-]);

    return ;

}

还有递归版：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

char s[];

int f[][];

bool mark[][];

bool pd(int l1,int r1,int l2,int r2)

{

    int k1=r1-l1+,k2=r2-l2+;

    if(k1%k2)return ;//前一个区间较长

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

        if(s[l1+i]!=s[l2+i%k2])return ;

    return ;

}

int cal(int x)

{

    int ret=;

    while(x)ret++,x/=;

    return ret;

}

int dp(int l,int r)

{

    if(l==r)return ;

    if(mark[l][r])return f[l][r];

    mark[l][r]=;

    int t=r-l+;

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

    {

        t=min(t,dp(l,i)+dp(i+,r));

        if(pd(l,i,i+,r))t=min(t,dp(l,i)++cal((i-l+)/(r-i)+));

    }

    return f[l][r]=t;

    }

int main()

{

    cin>>s;

    printf("%d",dp(,strlen(s)-));

    return ;

}

递归