先 orz oyds。但是为什么没有 oyds 的简单预处理做法啊。
区间 dp。\(dp_{i,j}\) 表示凑出区间 \([i,j]\) 的最小代价。考虑枚举当前区间 \([i,j]\) 与 \(k\)，表示 \([i,j]\) 在区间 \([p,j]\) 中出现了 \(k\) 次，且 \(p\) 取得最大值。则有转移：
\[\min(dp_{p,j},dp_{i,j}+B+k\times C+(j-p+1-k\times len)\times A)\to dp_{p,j} \]以及最基本的：
\[\min(dp_{i+1,j},dp_{i,j-1},dp_{i,j})\to dp_{i,j} \]这部分复杂度为 \(O(n\sum\frac{n}{i})=O(n^2\ln n)\)。
现在就要考虑怎么找这个 \(k\) 对应的 \(p\)。考虑维护 \(S\) 每两个后缀的 \(\operatorname{lcp}\)。简单 dp 即可。然后维护对于一对 \((i,k)\) 的 \(\min j\) 使得 \(\operatorname{lcp}(S[i:n],S[j:n])\ge k\)。这个东西可以先记录 \(=k\) 的情况，然后求后缀最大值。
这部分 \(O(n^2)\)。
简单好写。
code：
点击查看代码
int n,m,lcp[N][N],pre[N][N];
ll A,B,C,dp[N][N];
char s[N];
void Yorushika(){
scanf("%d%s%lld%lld%lld",&n,s+1,&A,&B,&C);
drep(i,n,1){
drep(j,i-1,1){
lcp[i][j]=s[i]==s[j]?lcp[i+1][j+1]+1:0;
lcp[i][j]=min(lcp[i][j],i-j);
if(!pre[i][lcp[i][j]])
pre[i][lcp[i][j]]=j;
}
drep(j,n,1){
pre[i][j]=max(pre[i][j],pre[i][j+1]);
}
}
mems(dp,0x3f);
rep(i,1,n){dp[i][i]=A;}
rep(len,1,n){
rep(i,1,n-len+1){
int j=i+len-1;
dp[i][j]=min({dp[i][j],dp[i+1][j]+A,dp[i][j-1]+A});
int p=i;
rep(k,1,j/len){
p=pre[p][len];
if(!p)break;
dp[p][j]=min(dp[p][j],dp[i][j]+B+(k+1)*C+(j-p+1-(k+1)*len)*A);
}
}
}
printf("%lld\n",dp[1][n]);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}