记录编号	137892	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	神奇的压缩机	最终得分	100
用户昵称	清羽	是否通过	通过
代码语言	C++	运行时间	0.135 s
提交时间	2014-11-05 13:40:51	内存使用	0.36 MiB

//by tsingyawn
/*
动态规划问题
状态定义：d[i]表示1~i压缩所付出的最小内存代价
状态转移方程：d[i]=min(d[i],d[i-1]+w1);
			  d[i]=min(d[i],d[k-1]+w2);
			  第二种转移需满足judge(k)>=i-k+1;
judge(i)表示从i开始如果可以复制的最大长度。judge可在预处理时计算
边界：d[0]=0，其余为INF。
*/
#include<cstdio>
#include<ctime>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=5000;

char s[maxn];
int d[maxn],w1,w2,n,judge[maxn];

void init()
{

	scanf("%s%d%d",s,&w1,&w2);
	n=strlen(s);
	memset(judge,0,sizeof(judge));
	for(int i=0;i<n;i++)//起点
	    for(int j=0;j<i;j++){//被复制的字符串起点
			int k=j,tot=0;
			while(i+tot<n && s[k]==s[i+tot]){
				tot++;
				k++;
				if(k>=i) k=j;
			}
			judge[i]=max(judge[i],tot);
	    }
}

void work()
{
	for(int i=0;i<n;i++){
		d[i]=(i==0)?w1:w1+d[i-1];
		for(int k=0;k<i;k++){
			if(judge[k]<i-k+1) continue;
			if(k!=0) d[i]=min(d[i],d[k-1]+w2);
			else d[i]=min(d[i],w2);
		}
//		printf("d[%d]=%d\n",i,d[i]);
	}
	printf("%d\n",d[n-1]);
}

int main()
{
	freopen("WinCHG.in","r",stdin);
	freopen("WinCHG.out","w",stdout);
	init();
	work();
	fclose(stdin);
	fclose(stdout);
	return 0;
}