没见过的区间dp
设 \(f_{i,j}\) 为 \(s[i,j]\) 能压缩成的最短长度。
首先可以用操作 A 转移 \(f_{i,j}=min(f_{i,j},f_{i,j-1}+A, f_{i+1,j}+A)\)
操作 B 和 C 是一回事，转移时枚举剪切的的子串，设当前剪切板里是 \(s[i,j]\)，则 \(f_{p,j}=min(f_{p,j}, f_{i,j} + k \times B + C \times k + A \times [j-p+1-k \times (j-i+1)])\)，其中 \(k\) 为 \(s[i,j]\) 在 \(s[p,j]\) 中出现的次数。注意到多余的转移是无意义的，所以 \(s[p,p+j-i] = s[i,j]\)。暴力枚举是会T的，考虑预处理出 \(pr_{i,j}\) 表示所有满足 \(lcp_{i,p} \ge j\) 的 \(p\) 的最大值，做一个 \(n^2\) 的 dp 即可。有转移 \(pr_{i,lcp_{i,p}}=max(pr_{i,lcp_{i,p}},p)\)，要注意这里转移的只是最长公共前缀，更短的部分可以继承它的 dp 值，因为一定有 \(pr_{i,j} \ge pr_{i,j+1}\)，所以要做一遍后缀 max。
#include<bits/stdc++.h>
using namespace std;
const int N=2600;
typedef long long ll;
int n,lcp[N][N],pr[N][N];
ll f[N][N],A,B,C;
string s;
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n>>s>>A>>B>>C;s='#'+s;for(int i=n;i>=1;i--){for(int j=i-1;j>=1;j--){if(s[i]==s[j])lcp[i][j]=lcp[i+1][j+1]+1;lcp[i][j]=min(lcp[i][j],i-j);pr[i][lcp[i][j]]=max(pr[i][lcp[i][j]],j);}for(int j=n;j>=1;j--)pr[i][j]=max(pr[i][j],pr[i][j+1]);}memset(f,0x3f,sizeof(f));for(int i=1;i<=n;i++)f[i][i]=A;for(int l=1;l<=n;l++){for(int i=1;i<=n-l+1;i++){int j=i+l-1;f[i][j]=min({f[i][j],f[i+1][j]+A,f[i][j-1]+A});for(int k=1,p=pr[i][l];p;p=pr[p][l],k++){f[p][j]=min(f[p][j],f[i][j]+B+(k+1)*C+(j-p+1-(k+1)*l)*A); }}}cout<<f[1][n];return 0;
}