知道是dp,但不会做
实验报告
题目背景
期末快要到了,will的大学物理实验报告还没有交,他向欧稳欧求助,欧稳欧丢给他一份照片版的实验报告就走了。现在will要将照片中的文字输入成电子版,由于时间紧迫,需要你来帮助他安排一种最快的输入方法。
题目描述
为了简化问题,实验报告文本由n个小写字母组成。
will可以执行三种操作:
- 花费a的时间,在末尾添加一个字符
- 花费b的时间,删除末尾的一个字符
- 花费c的时间,复制当前输入的所有字符,然后粘贴在末尾
你需要计算,输入这n个字符最少需要花费多少时间。(注意:在输入的过程中总字符数可能会超过n)
输入格式
第一行输入三个整数a,b,c,分别表示三种操作需要的时间。
第二行输入一个字符串,表示需要输入的文本。
输出格式
一行一个整数,表示最少花费的时间。
样例 #1
样例输入 #1
1 3 2
aaaaaabaaaaaa
样例输出 #1
11
提示
样例的解释:
先输入3个a
,然后复制粘贴,接着输入一个b
,再复制粘贴,最后删除末尾的b
。总时间为1+1+1+2+1+2+3=11。
数据范围
对于前30%的数据,a=b=c=1,且所有字符都为a
;
对于另外30%的数据,a=1,b=105,c=1;
对于100%的数据,1≤n≤5000,1≤a,b,c≤105。