记录编号	159865	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	神奇的压缩机	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.140 s
提交时间	2015-04-22 21:02:08	内存使用	0.36 MiB

//版权清羽所有，本人纯属借鉴
#include <fstream>
#include <string.h>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream in("WinCHG.in");
ofstream out("WinCHG.out");
int f[5001]={0},q[5001]={0},a,b;
char s[5001]={0};
int n;
int main()
{
	int i,j,k,ans=0;
	f[0]=1;
	in>>s>>a>>b;
	n=strlen(s);
	//for(i=0;i<n-1;i++)out<<s[i]<<endl;
	for(i=0;i<n;i++)
	{
		for(j=0;j<i;j++)
		{
			k=j;ans=0;
			while(i+ans<n&&s[k]==s[i+ans])
			{
				ans++;
				k++;
				if(k>=i)k=j;
			}
			q[i]=max(q[i],ans);
		}
	}
	for(i=0;i<n;i++)
	{
		f[i]=(i==0)?a:a+f[i-1];
		//out<<f[i]<<' ';
		for(k=0;k<i;k++)
		{
			if(q[k]<i-k+1)continue;
			if(k)f[i]=min(f[i],f[k-1]+b);
			else f[i]=min(f[i],b);
		}
	}
	//for(i=0;i<n;i++)out<<f[i]<<endl;
	out<<f[n-1]<<endl;
	return 0;
}