记录编号	138056	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	神奇的压缩机	最终得分	100
用户昵称	ggwdwsbs	是否通过	通过
代码语言	C++	运行时间	0.218 s
提交时间	2014-11-05 16:48:24	内存使用	1.02 MiB

/*
状态:f[i][j]表示从i开始到j所需的最小内存;
状态转移方程:f[i][j]=max(f[i],f[i-1]+a,f[i-d[i]]+b);
预处理:d[i]表示从i起最长,枚举i(复制出来的串起点),j(被复制的串起点);
*/
#include<stdio.h>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int n;
int d[100001];
int f[100001];
int a,b;
string s;
int min(int x,int y)
{
	if(x>y) return y;
	else return x;
}
int max(int x,int y)
{
	if(x>y) return x;
	else return y;
}
void init()//get d[];
{
	for(int i=0;i<n;i++)
	 for(int j=0;j<=i;j++)
	 {
		int l=j,r=i+1,t=0;
		while(r<n&&s[l]==s[r])
		{
			//if(i==1) printf("%d %d\n",l,r);
			r++;
			l++;
			t++;
			if(l>i) l=j;
		}
		d[i]=max(d[i],t);
	 }
	//for(int i=0;i<n;i++)
	// printf("%d %d\n",i,d[i]);
}
int main()
{
	freopen("WinCHG.in","r",stdin);
	freopen("WinCHG.out","w",stdout);
	cin>>s;
	n=s.size();
	init();
	scanf("%d%d",&a,&b);
	memset(f,127/3,sizeof(f));
	f[0]=a;
	for(int i=0;i<n;i++)
	{
		f[i]=min(f[i],f[i-1]+a);
		for(int j=0;j<i;j++)
		 if(d[j]+j>=i)
		  f[i]=min(f[j]+b,f[i]);
	}
	printf("%d",f[n-1]);
	//while(1);
}