求条 70pts

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=105;
int n,dp[N][N][2];
string s,t;

signed main()
{
    cin>>s;
    n=s.size();
    s=" "+s;
    memset(dp,0x3f,sizeof dp);
    for(int i=1;i<=n;i++)
        dp[i][i][0]=1,dp[i][i][1]=3;
    for(int len=2;len<=n;len++)
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            for(int k=i;k<j;k++)
            {
                dp[i][j][0]=min(dp[i][j][0],dp[i][k][0]+min(dp[k+1][j][0],dp[k+1][j][1]));
                dp[i][j][1]=min(dp[i][j][1],dp[i][k][1]+min(dp[k+1][j][0],dp[k+1][j][1]));
            }
            if(len%2!=0)
                continue;
            int pos=i+len/2;
            if(s.substr(i,len/2)==s.substr(pos,len/2))
                dp[i][j][1]=min(dp[i][j][1],min(dp[i][pos-1][1]-1,dp[i][pos-1][0])+2);
        }
    cout<<min(dp[1][n][0],dp[1][n][1]-1);
    return 0;
}