Codeforces Round #543 (Div. 2, based on Technocup 2019 Final Round) F. Compress String(暴力dp处理LCS)

拿到这题一看，嗯？SAM？

仔细一看，嗯？n这么小啊，暴力dp处理LCS就完事了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e3+5;
int dp[maxn][maxn];
int ans[maxn];
char s[maxn];
int main()
{
    int n,a,b;
    scanf("%d%d%d",&n,&a,&b);
    scanf("%s",s+1);
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(s[i]==s[j]) dp[i][j]=dp[i-1][j-1]+1;
        }
        ans[i]=INT_MAX;
        for(int j=0;j<i;j++)
        {
            int x=min(i-j,dp[i][j]);
            if(x>0) ans[i]=min(ans[i],ans[i-x]+b);
        }
        ans[i]=min(ans[i],ans[i-1]+a);
    }
    printf("%d\n",ans[n]);
}

当然SAM也能写，有空的话就补上SAM版