记录编号	287485	评测结果	AAAAAAAAAA
题目名称	[SCOI 2007]压缩	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-08-01 20:23:13	内存使用	0.34 MiB

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int f[55][55][2];
string s;
bool match(int l,int r){
	int len=(r-l+1);
	if(len&1) return 0;
	for(int i=l;i<=(l+r)/2;i++)
		if(s[i]!=s[i+len/2]) return 0;
	return 1;
}
int dp(int l,int r,bool flag){
	int tmp=r-l+1;
	if(l>r) return 0;
	if(l==r) return 1;
	if(f[l][r][flag]) return f[l][r][flag];
	if(flag)for(int i=l;i<r;i++) tmp=min(tmp,dp(l,i,1)+dp(i+1,r,1)+1);
	for(int i=l;i<r;i++) tmp=min(tmp,dp(l,i,flag)+r-i);
	if(match(l,r)) tmp=min(tmp,dp(l,(l+r)/2,0)+1);
	return f[l][r][flag]=tmp;
}
int main(){
	freopen("compress.in","r",stdin);freopen("compress.out","w",stdout);
	cin>>s;int len=s.length();s=' '+s;
	printf("%d",dp(1,len,1));
	return 0;
}