P9523 [JOISC 2022 Day2] 复制粘贴 3 题解
寻逍遥2006
·
·
题解
传送门
简要题意：
我们可以进行以下的三种操作维护两个字符串 X 和 Y：
- 在 X 的末尾加入一个字符 c，需要 A 的代价。
- 将 Y 变成 X，同时将 X 清空，需要 B 的代价。
- 在 X 末尾插入一个字符串 Y，需要 C 的代价。
最后要求 X 串为一个特定的串 S。
记 S[l,r] 为 S 的第 l 位到第 r 位构成的字符串。
首先，X 和 Y 必然是 S 的子串，因为不是 S 子串的 X，Y 必然会在某一次剪切之后被覆盖掉，这样是劣于不做这些操作。
考虑一个朴素的动态规划方法，记 f_{l_x,r_x,l_y,r_y} 表示从 X=Y=\varnothing 操作到 X=S[l_x,r_x],Y=S[l_y,r_y] 的最少代价。
最后的答案即为 f_{1,n,*,*}，转移有三种：
-
-
-
第三种转移的可行性使用任意字符串方式查询即可做到 O(n^4)。
显然，这样的做法是过不了的，所以考虑怎么优化复杂度。
首先 l_x 和 r_x 是看起来不可优化的，所以考虑将 l_y 和 r_y 优化掉。我们把 1 和 3 类转移合并在一起，也就是，我们把 Y 变成 X 之后，我们直接将 X 变成由 Y 和若干其他字符组成的字符串。下一次要转移，就是再次将 Y 变成 X，然后重复上述操作。
这样可以之间将 l_y 和 r_y 这两位去掉。
考虑现在的转移是什么，除了可以粘贴 Y 的部分，由必须用 A 将其余的位置填满，所以写出转移式：
其中 $cnt$ 为从 $S[l,r]$ 中取出多少个互不相交的 $S[l',r']$。由于取出现靠前的 $S[l',r']$ 一定比取靠后的 $S[l',r']$ 优，所以 $cnt$ 的上界就是从 $S[l,r]$ 中贪心取 $S[l',r']$ 的个数。
对于转移移项得：
$f_{l,r}=A\times (r-l+1)+B+f_{l',r'}+cnt\times [C-A\times (r'-l'+1)]$。
其中第一项只与 $l,r$ 有关了，第二项为常数，第三项只与 $l',r'$ 有关，现在需要考虑第四项的问题。
和两遍都挂勾的就是 $cnt$，所以考虑怎么处理 $cnt$。
我们可以钦定 $l',r'$ 是 $S[l,r]$ 中子串 $S[l',r']$ 第一次出现的位置。这样，对于固定的 $cnt$，我们可以得到 $r$ 的一个下界：就是从第 $l'$ 位开始，贪心取出互不相交的 $S[l',r']$，第 $cnt$ 个串位置的右边界 $R$。
又因为 $l\leqslant l'$，所以对于这组 $(l',r',cnt)$ 的转移可以转移到任意 $l\leqslant l',R\leqslant r$ 的位置。
考虑如何求出 $R$，我们可以维护一个数组 $nxt_{l',r'}$，表示最小的 $k>r'$，满足 $S[k,k+r'-l']=S[l'.r']$。我们就可以通过跳 $nxt$ 数组来通过 $(l',r',cnt-1)$ 的 $R'$ 得到 $(l',r',cnt)$ 的 $R$，具体的，$R=nxt_{R-r'+l',R}+r'-l'$。
$nxt$ 数组可以使用后缀自动机上维护线段树合并来做到 $O(N^2\log N)$ 维护，相当于就是 $O(N^2)$ 次查线段树上的区间最小值。
那么现在的转移相当于是一个二维的矩阵取 $\min$，发现通过 $l$ 单调递减，$r$ 单调递增的方式维护转移，可以直接使用树状数组维护前缀 $\min$。
现在的时间复杂度为 $O(G\log n)$ 其中 $G$ 为可行的 $(l',r',cnt)$ 的数量，记对于 $l',r'$ 最大的 $cnt$ 为 $t_{l',r'}$，相当于求 $\sum\limits_{l}\sum\limits_{r}t_{l,r}$。
考虑证明它的上界，显然 $t_{l,r}\leqslant \dfrac{n-r}{r-l+1}$。
所以 $G\leqslant \sum\limits_{l}\sum\limits_{r}\dfrac{n-r}{r-l+1}=\sum\limits_{r}(n-r)\sum\limits_{l}\dfrac{1}{r-l+1}\approx\sum\limits_{r}(n-r)\ln r=O(n^2\ln n)$。
所以总体复杂度为 $O(n^2\ln n\log n)$，常数很小，跑起来飞快。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
int Qread()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return x;
}
char get_ch()
{
char ch=getchar();
while(ch<'a'||ch>'z') ch=getchar();
return ch;
}
int N;
long long A,B,C;
namespace BIT{
long long num[2501];
void add_num(int x,long long a){for(;x<=N;x+=(x&-x)) num[x]=min(num[x],a);}
long long get_min(int x){long long ret=0;for(;x;x-=(x&-x)) ret=min(ret,num[x]);return ret;}
}
#define mid (l+r>>1)
#define ls s[pos].lson
#define rs s[pos].rson
namespace Sege{
struct Node{
int num,lson,rson;
}s[50010];
int poi_cnt;
void add_num(int x,int &pos,int l=1,int r=N)
{
if(!pos) pos=++poi_cnt;
s[pos].num=x;
if(l==r) return;
if(x<=mid) return add_num(x,ls,l,mid);
else return add_num(x,rs,mid+1,r);
}
void merge(int &pos,int pos_,int l=1,int r=N)
{
if(pos&&pos_)
{
if(l==r) s[pos].num=min(s[pos].num,s[pos_].num);
else merge(ls,s[pos_].lson,l,mid),merge(rs,s[pos_].rson,mid+1,r),s[pos].num=min(s[ls].num,s[rs].num);
}
else pos+=pos_;
}
int range_min(int L,int R,int pos,int l=1,int r=N)
{
if(L<=l&&r<=R) return s[pos].num;
if(r<L||R<l) return N+1;
return min(range_min(L,R,ls,l,mid),range_min(L,R,rs,mid+1,r));
}
}
#undef mid
#undef ls
#undef rs
namespace SAM{
struct Node{
int link,len,rt;
int nxt[26];
}s[5010];
int poi_cnt;
vector<int> son[5010];
int insert_node(int ind,int las,int nw)
{
int cur=++poi_cnt;
Sege::add_num(ind,s[cur].rt);
s[cur].len=s[las].len+1;
int p=las;
while(p!=-1&&!s[p].nxt[nw])
{
s[p].nxt[nw]=cur;
p=s[p].link;
}
if(p==-1) s[cur].link=0;
else
{
int q=s[p].nxt[nw];
if(s[q].len==s[p].len+1) s[cur].link=q;
else
{
int clo=++poi_cnt;
s[clo].len=s[p].len+1;
s[clo].link=s[q].link;
memcpy(s[clo].nxt,s[q].nxt,sizeof(s[q].nxt));
while(p!=-1&&s[p].nxt[nw]==q)
{
s[p].nxt[nw]=clo;
p=s[p].link;
}
s[q].link=s[cur].link=clo;
}
}
return cur;
}
void get_fa()
{
for(int i=1;i<=poi_cnt;i++)
son[s[i].link].push_back(i);
}
}
char S[2501];
long long f[2510][2501];
int nxt[2510][2510];
#define mid (l+r>>1)
void solve(int rt,int pos,int L,int R,int l=1,int r=N)
{
if(!pos) return;
if(l==r)
{
for(int i=L;i<=R;i++)
{
// printf("find(%d %d)",l-i)
nxt[l-i+1][l]=Sege::range_min(l+i,N,rt);
}
}
solve(rt,Sege::s[pos].lson,L,R,l,mid);
solve(rt,Sege::s[pos].rson,L,R,mid+1,r);
}
#undef mid
void dfs(int a)
{
for(int v: SAM::son[a])
{
dfs(v);
Sege::merge(SAM::s[a].rt,SAM::s[v].rt);
}
if(a) solve(SAM::s[a].rt,SAM::s[a].rt,SAM::s[SAM::s[a].link].len+1,SAM::s[a].len);
}
int main()
{
N=Qread();
Sege::s[0].num=N+1;
SAM::s[0].link=-1;
for(int i=1;i<=N;i++)
S[i]=get_ch();
A=Qread(),B=Qread(),C=Qread();
for(int i=1,las=0;i<=N;i++)
las=SAM::insert_node(i,las,S[i]-'a');
SAM::get_fa();
dfs(0);
for(int l=N;l;l--)
for(int r=l;r<=N;r++)
{
int len=r-l+1;
f[l][r]=A*len+min(0ll,B+BIT::get_min(r));
int cur=r,cnt=1;
while(cur<=N)
{
BIT::add_num(cur,cnt*(C-A*len)+f[l][r]);
cur=nxt[cur-len+1][cur],cnt++;
}
}
printf("%lld\n",f[1][N]);
return 0;
}
```