记录编号	137782	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	神奇的压缩机	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.719 s
提交时间	2014-11-05 09:59:18	内存使用	0.39 MiB

//Verdict: Accepted 2 // Submission Date: 2014-10-02 16:34:32
// Time: 8256MS
// Memory: 34624KB

/*=============================================================================================================================*/
/*======================================================Code by Asm.Def========================================================*/
/*=============================================================================================================================*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <memory.h>
#include <cstring>
#include <cstdlib>
using namespace std;
#define maxn ((int)4.1e3)
/*===========================================================TYPES=============================================================*/
typedef long long LL;
  
/*======================================================GLOBAL VARIABLES=======================================================*/
char ch[maxn];
int len = 0, minbit[maxn], *next[maxn];
int l[maxn], r[maxn], str[maxn];
/*==========================================================FUNCTIONS==========================================================*/
inline void getnext(int l){
    int i, j, L = len - l;
    next[l] = new int[L+2];
    int *Next = next[l];
    Next[0] = 0;
    for(i = 1;i < L;++i){
        j = Next[i-1] - 1;
        while(ch[l+i] != ch[l+j+1] && j >= 0)
            j = Next[j] - 1;
        if(ch[l+i] == ch[l+j+1])
            Next[i] = j + 2;
        else Next[i] = 0;
    }
}
int A, B;

int main(){
    #ifdef DEBUG
    freopen("test","r",stdin);
	#else
	freopen("WinCHG.in", "r", stdin);
	freopen("WinCHG.out", "w", stdout);
    #endif
    char c = getchar();
	while(!isalpha(c))c = getchar();
    while(isalpha(c))str[len] = len, ch[len++] = c, c = getchar();
	cin >> A >> B;
    int i, j, Min, t;
    for(i = 0;i < len - 1; ++i)
        getnext(i);
    minbit[0] = A;
    for(i = 1;i < len; ++i){
        Min = 0x7fffffff;
        for(j = 0;j < i;++j)
            if(minbit[j] + (i-j) * A < Min){
                Min = minbit[j] + (i-j) * A;
                str[i] = i;
                r[i] = j+1;
            }
        for(j = 0;j < i; ++j){
            t = next[j][i-j];
            if(!t)continue;
            if(minbit[i-t] + B < Min){
                Min = minbit[i-t] + B;
                str[i] = i-t;
                r[i] = i+1-t-j;
                l[i] = t;
            }
        }
        minbit[i] = Min;
    }
    printf("%d\n", minbit[len-1]);
    return 0;
}
/*============================================================*/