[CF1120C] Compress String

Description

给定一个长度为 (n (n le 5000)) 的字符串，要求将其划分为若干段。每一段要么长度为 (1)，要么是本段之前部分的子串。前者代价为 (a)，后者代价为 (b)，求最小总代价。

Solution

设 (f[i]) 表示划分完 (s[1..i]) 的最小总代价，则有

[f[i]=min(f[i-1]+a, min_{j<i, s[j+1..i] subseteq s[1..j]} f[j]+b) ]

考虑到 (f[]) 具有单调性，因此在第二种转移中，(j) 一定要尽可能大，设 (LCS(i,j)) 表示 (s[1..i]) 与 (s[1..j]) 的最长公共后缀，则有

[f[i]=min(f[i-1]+a, min_{j<i} (f_{max (j, i-LCS(i,j))})) ]

而 (LCS(i,j)) 可以很轻易地用 SA 求出，事实上，由于

[egin {aligned} & LCS(i,j) = 0, & s[i] eq s[j] \ & LCS(i,j)=LCS(i-1,j-1)+1, & s[i]=s[j] end {aligned} ]

可以在 (O(n^2)) 时间内预处理出 (LCS(i,j))，故总时间复杂度为 (O(n^2))

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 5005;

int f[N],lcs[N][N];
char s[N];
int n,a,b;

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>a>>b>>s+1;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(s[i]==s[j])
            {
                lcs[i][j]=lcs[i-1][j-1]+1;
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        f[i]=f[i-1]+a;
        for(int j=1;j<i;j++)
        {
            f[i]=min(f[i], f[max(j,i-lcs[i][j])]+b);
        }
    }

    cout<<f[n]<<endl;
}