思路

令 $f_{l,r}$ 表示区间 $[l,r]$ 的最小代价。初始化 $f_{i,i}=A$。

我们考虑 $n^3$ 的做法（是的你没听错跑的飞快）。

首先预处理 hash，用来判断两个字串是否相等，方便我们判断可否复制。

我们枚举 $l,r$ 两个端点及其长度 $len$，考虑 $f_{l,r}$ 如何被转移，我们直接从前面或者后面加一个字符，代价为 $A$，则有 $f_{l,r}\to \min (f_{l+1,r},f_{l,r-1})+A$

我们考虑剪切和复制该如何转移，对于复制和剪切我们从题中可得只更改后面的字符，那么我们只要从 $l$ 开始进行转移即可，对于区间 $[l,r]$ 的剪切代价为 $B$，然后我们接着又开始枚举一个指针 $k$，我们用 hash 判断是否可以复制，如果可以复制我们就直接代价加 $C$，然后 $k\to k+len-1$，不可以复制那么就直接代价加 $A$，$k\to k+1$，令总代价为 $sum$，则有 $f_{l,k}\to f_{l,r}+sum$。

#include<bits/stdc++.h>
#define int unsigned long long
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=2510,base=131;
int f[N][N];
int n,A,B,C;
int hs[N],g[N];
char s[N];
int calc(int l,int r){
	return hs[r]-hs[l-1]*g[r-l+1];
}
signed main(){
	cin>>n>>(s+1)>>A>>B>>C;
	memset(f,0x3f,sizeof f);
	g[0]=1;
	rep(i,1,n) hs[i]=hs[i-1]*base+s[i],g[i]=g[i-1]*base,f[i][i]=A;
	rep(len,1,n){
		for(int l=1,r=l+len-1;r<=n;++l,++r){
			if(len>1){
				f[l][r]=min({f[l][r],f[l+1][r]+A,f[l][r-1]+A});
			}
			int h=calc(l,r),sum=B;
			rep(k,l,n-len+1){
				if(calc(k,k+len-1)==h){
					k+=len-1;
					sum+=C;
					f[l][k]=min(f[l][k],f[l][r]+sum);
				}else{
					sum+=A;
				}
			}
		}
	}
	cout<<f[1][n];
	return 0;
}