CF1120 C. Compress String(SAM+DP)

有方程dp[i]=min(dp[i-1]+A,dp[j]+B);如果s[j+1,i]在s[i,j]中出现,所以我们就是要知道每个子串在s出现的第一个位置,这个可以hash实现或者sam,或者kmp实现。

pos[i][j]表示s[i,j]对应的sam的位置,occ[],表示第一次出现的位置。

#include<bits/stdc++.h>
#define ll long long
#define rep2(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
char c[maxn],s[maxn];
struct SAM{
int ch[maxn][],fa[maxn],maxlen[maxn],cnt,last;
int a[maxn],b[maxn],occ[maxn];
void init()
{
cnt=last=;
memset(ch[],,sizeof(ch[]));
memset(occ,0x3f,sizeof(occ));
}
int add(int x,int pos)
{
int np=++cnt,p=last; last=np; occ[np]=pos;
maxlen[np]=maxlen[p]+;memset(ch[np],,sizeof(ch[np]));
while(p&&!ch[p][x]) ch[p][x]=np,p=fa[p];
if(!p) fa[np]=;
else {
int q=ch[p][x];
if(maxlen[q]==maxlen[p]+) fa[np]=q;
else {
int nq=++cnt; maxlen[nq]=maxlen[p]+;
fa[nq]=fa[q]; fa[q]=fa[np]=nq;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
while(p&&ch[p][x]==q) ch[p][x]=nq,p=fa[p];
}
}
}
void Sort()
{
rep(i,,cnt) a[i]=;
rep(i,,cnt) a[maxlen[i]]++;
rep(i,,cnt) a[i]+=a[i-];
rep(i,,cnt) b[a[maxlen[i]]--]=i;
for(int i=cnt;i>=;i--)
occ[fa[b[i]]]=min(occ[b[i]],occ[fa[b[i]]]);
}
}T;
int a[maxn],A,B,dp[maxn],pos[][];
int main()
{
int N;
scanf("%d%d%d%s",&N,&A,&B,c+);
T.init();
rep(i,,N) T.add(c[i]-'a',i);
rep(i,,N) {
int now=;
rep(j,i,N){
now=T.ch[now][c[j]-'a'];
pos[i][j]=now;
}
}
T.Sort();
rep(i,,N){
dp[i]=dp[i-]+A;
rep(j,,i-){
if(T.occ[pos[j+][i]]<=j){
dp[i]=min(dp[i],dp[j]+B);
break;
}
}
}
printf("%d\n",dp[N]);
return ;
}
上一篇:es5 and es6


下一篇:Unity安装问题