P9523

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

区间 dp。 $dp_{i,j}$ 表示凑出区间 $[i,j]$ 的最小代价。考虑枚举当前区间 $[i,j]$ 与 $k$ ，表示 $[i,j]$ 在区间 $[p,j]$ 中出现了 $k$ 次，且 $p$ 取得最大值。则有转移：

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

以及最基本的：

\min(dp_{i+1,j},dp_{i,j-1},dp_{i,j})\to dp_{i,j}

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

现在就要考虑怎么找这个 $k$ 对应的 $p$ 。考虑维护 $S$ 每两个后缀的 $\operatorname{lcp}$ 。简单 dp 即可。然后维护对于一对 $(i,k)$ 的 $\min j$ 使得 $\operatorname{lcp}(S[i:n],S[j:n])\ge k$ 。这个东西可以先记录 $=k$ 的情况，然后求后缀最大值。

这部分 $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();
}

感谢您的支持，我会继续努力的!