学步园

http://www.lydsy.com/JudgeOnline/problem.php?id=1068

一定要对题意理解透彻，不然就会像我一样一直wa

开始没有考虑一种很特殊的情况，就是开头会有M，wa了3组，70分

后来把DP全改了，但还是有点错误，90分

最后看了遍题，，，才AC、、、、、、

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive
************************************************/
/////////////////////////////////////////////////
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int getint()
{
    int r=0,k=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
    for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';
    return k*r;
}
/////////////////////////////////////////////////
char s[55];
int n;

int dp[55][55][2];
/*
dp[l][r][]:[l,r]的最小长度
0:不能有M
1:可有可无 
*/
/////////////////////////////////////////////////
bool check(int l,int r,int L,int R)
{
	int tmp=l;
    rep(cur,L,R)
    {
    	if(s[cur]!=s[tmp]) return 0;
    	tmp++;
    	if(tmp==r+1) tmp=l;
    }
    return 1;
}
//70分 
/*int DP(int l,int r,bool M)
{
	if(dp[l][r][M]!=-1) return dp[l][r][M];
	if(l==r) return dp[l][r][M]=1;
	int len=r-l+1;
	int ans=0x3fffffff;
	int add=M?1:2;
	if(len>2 && !(len&1))
	{
		int m=l+len/2-1;
		if(check(l,m,m+1,r))
		    ans=min(ans,DP(l,m,0)+add);
	}
	rep(m,l,r-1)
	{
		//[l,m] [m+1,r]
		ans=min(ans,DP(l,m,M)+DP(m+1,r,0));
	}
    //printf("dp[%d][%d]=%d\n",l,r,ans);
	return dp[l][r][M]=ans;
}*/
//90分 
/*int DP(int l,int r,bool M)
{
	if(dp[l][r][M]!=-1) return dp[l][r][M];
	if(l==r) return 1;
	int len=r-l+1;
	int ans=0x3fffffff;
	if(len>2 && !(len&1))
	{
		int m=l+len/2-1;
		if(check(l,m,m+1,r))
		    ans=min(ans,DP(l,m,0)+1);
	}
	if(M) rep(m,l,r-1) ans=min(ans,DP(l,m,1)+DP(m+1,r,1)+1);
	rep(m,l,r-1) ans=min(ans,DP(l,m,1)+r-m);
	return dp[l][r][M]=ans;
}*/
int DP(int l,int r,bool M)
{
	if(dp[l][r][M]!=-1) return dp[l][r][M];
	if(l==r) return 1;
	int len=r-l+1;
	int ans=0x3fffffff;
	if(len>2 && !(len&1))
	{
		int m=l+len/2-1;
		if(check(l,m,m+1,r))
		    ans=min(ans,DP(l,m,0)+1);
	}
	if(M) rep(m,l,r-1) ans=min(ans,DP(l,m,1)+DP(m+1,r,1)+1);
	rep(m,l,r-1) ans=min(ans,DP(l,m,M)+r-m);
	return dp[l][r][M]=ans;
}
/////////////////////////////////////////////////
void input()
{
    scanf("%s",s+1);
    n=strlen(s+1);
}
void solve()
{
    MS(dp,-1);
    printf("%d\n",DP(1,n,1));
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("std.out","w",stdout);
    #endif
    input();
    solve();
    return 0;
}