P2470

区间DP。

区间$DP$

#include <bits/stdc++.h>
#define ll long long
#define maxn 55
using namespace std;
string nw;
ll len,dp[maxn][maxn][3];
//dp[x][y][1/0]表示在x到y区间内是/否有m的最小长度
//nw是原字符串

inline int check(ll l,ll r){
    if((r-l+1)&1)   return 0;
    ll mid=(l+r)>>1;
    for(register int i=l;i<=mid;++i)
        if(nw[i]!=nw[i+mid-l+1])//i+mid-l-1自己手动模拟以下是可以判重复的
            return 0;
    return 1;
}

int main(){
    cin>>nw;
    len=nw.size();//获得字符长度
    memset(dp,0x3f,sizeof(dp));//清最大值
    for(register int i=1;i<=len;++i)
        for(register int j=i;j<=len;++j)
            dp[i][j][0]=dp[i][j][1]=(j-i+1);//初始值都是段落长度（m留给下面处理了这里并不需要将dp[i][j][1]加上1
    for(register int l=2;l<=len;++l)
        for(register int i=1;i+l-1<=len;++i){
            ll j=i+l-1;
            if(check(i-1,j-1))
                dp[i][j][0]=min(dp[i][(i+j)>>1][0]+1,dp[i][j][0]);//如果有重叠的那么加上R（这里在前面那一段使用的是不含m的段，如果有m的话那么就会导致重复部分混乱），至于m会在下面处理这里并不需要管
            for(register int k=i;k<j;++k)
                dp[i][j][0]=min(dp[i][j][0],dp[i][k][0]+(j-k));//如果没有m：直接在后面拼上一截，如果后面那一段有折叠的话，会在下面那个循环(dp[i][j][1])中处理
            for(register int k=i;k<j;++k)
                dp[i][j][1]=min(dp[i][j][1],min(dp[i][k][0],dp[i][k][1])+min(dp[k+1][j][0],dp[k+1][j][1])+1);
                //k枚举的为m的位置，在前半段和后半段中分别取出一个最小的再在中间加上m（至于具体的R的位置并不需要管因为后面那一段如果有重复的话那么dp[k+1][j][1]肯定是小于dp[k+1][j][0]的）；如果后面那一段不可以折叠的话那么dp[i][j][0]肯定是小于dp[i][j][1]的（毕竟dp[i][j][1]要多一个1）
        }
    printf("%lld\n",min(dp[1][len][1],dp[1][len][0]));//最后输出最优的解
    return 0;
}
//最优划分只有一种，最小划分也一定是最优划分并且满足局部段落最小划分
复制代码