自动搬运

查看原文

来自洛谷，原作者为

	shinkuu Dreams are the seedlings of realities.

搬运于2025-08-24 22:49:11，当前版本为作者最后更新于2023-10-07 19:55:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

先 orz oyds。但是为什么没有 oyds 的简单预处理做法啊。

区间 dp。$dp_{i,j}$ 表示凑出区间 $[i,j]$ 的最小代价。考虑枚举当前区间 $[i,j]$ 与 $k$，找到一个最大的 $p$，使得 $[i,j]$ 在区间 $[p,j]$ 中不重叠地出现了 $k$ 次。则有转移：

$$dp_{p,j}\leftarrow\min(dp_{p,j},dp_{i,j}+B+k\times C+(j-p+1-k\times len)\times A) $$

以及最基本的：

$$dp_{i,j}\leftarrow\min(dp_{i+1,j}+A,dp_{i,j-1}+A,dp_{i,j}) $$

这部分复杂度为 $O(\sum\frac{n}{j-i+1})=O(n^2\ln n)$。

现在就要考虑怎么找这个 $k$ 对应的 $p$。考虑 dp 求出 $S$ 每两个后缀的 $\operatorname{lcp}$，然后处理出对于一对 $(i,k)$ 的最大的 $j<i$，使得 $\operatorname{lcp}(S[i:n],S[j:n])\ge k$。这个东西可以先记录 $=k$ 的情况，然后求后缀最大值。注意此处由于两个串不能重叠，所以预处理时令 $\operatorname{lcp}(S[i:n],S[j:n])\le i-j$。

这部分 $O(n^2)$。

简单好写。

code：

int n,m,lcp[N][N],pre[N][N];
ll A,B,C,dp[N][N];
char s[N];
void Yorushika(){
	scanf("%d%s%lld%lld%lld",&n,s+1,&A,&B,&C);
	drep(i,n,1){
		drep(j,i-1,1){
			lcp[i][j]=s[i]==s[j]?lcp[i+1][j+1]+1:0;
			lcp[i][j]=min(lcp[i][j],i-j);
			if(!pre[i][lcp[i][j]])
				pre[i][lcp[i][j]]=j;
		}
		drep(j,n,1){
			pre[i][j]=max(pre[i][j],pre[i][j+1]);
		}
	}
	mems(dp,0x3f);
	rep(i,1,n){dp[i][i]=A;}
	rep(len,1,n){
		rep(i,1,n-len+1){
			int j=i+len-1;
			dp[i][j]=min({dp[i][j],dp[i+1][j]+A,dp[i][j-1]+A});
			int p=i;
			rep(k,1,j/len){
				p=pre[p][len];
				if(!p)break;
				dp[p][j]=min(dp[p][j],dp[i][j]+B+(k+1)*C+(j-p+1-(k+1)*len)*A);
			}
		}
	}
	printf("%lld\n",dp[1][n]);
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}

upd 11.27：修改了若干错误。