专栏文章

题解：CF150D Mission Impassable

AA6n6d6y6
CF150D题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miov1sw0
此快照首次捕获于
2025/12/03 01:37
3 个月前
此快照最后确认于
2025/12/03 01:37
3 个月前
查看原文

题意

有一个字符串 ss，每次操作可以删掉长度为 ii 的回文子串并获得 viv_i 的分数。
特别地，vi=−1v_i=−1 代表不能删除长度为 ii 的串。
操作完之后将删除位置前后字符串拼接起来。
重复操作若干次，问最多能获得多少分数。

思路

vi=−1v_i=−1 时懒得特判，只需设为 vi=−∞v_i=-\infty 即可。
套路地，尝试区间 DP，设 hl,rh_{l,r} 表示将 [l,r][l,r] 操作若干次后，能获得的最大分数。
那么有 hl,r=max⁡{0,hl,p+hq,r}h_{l,r}=\max\{0,h_{l,p}+h_{q,r}\}，其中 l≤p<q≤rl\le p\lt q\le r，但是并不知道初始值。
不妨设 fl,rf_{l,r} 为将 [l,r][l,r] 全部删除后能获得的最大分数，可以证明，这一定能做到。
此时 hl,rh_{l,r} 的初始值就是 fl,rf_{l,r}，即 hl,r=max⁡{0,fl,r,hl,p+hq,r}h_{l,r}=\max\{0,f_{l,r},h_{l,p}+h_{q,r}\}，其中 l≤p<q≤rl\le p\lt q\le r。
考虑转移 fl,rf_{l,r}，显然有 fl,r=max⁡{fl,p+fp+1,r}f_{l,r}=\max\{f_{l,p}+f_{p+1,r}\}，其中 l≤p<rl\le p\lt r，问题仍在。
如何处理回文串的转移？考虑再设 gl,r,kg_{l,r,k} 表示将 [l,r][l,r] 删到只剩一个长度为 kk 的回文串后获得的最大分数。
那么 fl,rf_{l,r} 就可以看作 gl,r,0g_{l,r,0}，即为 max⁡{gl,r,k+ak}\max\{g_{l,r,k}+a_k\}，其中 1≤k≤r−l+11\le k\le r-l+1（不过下面仍然会区分 fl,rf_{l,r} 和 gl,r,0g_{l,r,0}）。
如果 sl=srs_l=s_r，那么 gl,r,kg_{l,r,k} 可以从 gl+1,r−1,k−2g_{l+1,r-1,k-2} 转移；也可以枚举断点，分讨回文串来自断点左右侧从而转移。
综上：
ff 的转移式为：fl,r=max⁡{gl,r,k+ak,fl,p+fp+1,r}f_{l,r}=\max\{g_{l,r,k}+a_k,f_{l,p}+f_{p+1,r}\}，其中 1≤k≤r−l+1,l≤p<r1\le k\le r-l+1,l\le p\lt r。
gg 的转移式为：gl,r,k=max⁡{fl,p+gp+1,r,k,gl,p,k+fp+1,r,[k≥2∧sl=sr]gl+1,r−1,k−2}g_{l,r,k}=\max\{f_{l,p}+g_{p+1,r,k},g_{l,p,k}+f_{p+1,r},[k\ge 2\land s_l=s_r]g_{l+1,r-1,k-2}\}，其中 l≤p<rl\le p\lt r。
hh 的转移式为：hl,r=max⁡{0,fl,r,hl,p+hq,r}h_{l,r}=\max\{0,f_{l,r},h_{l,p}+h_{q,r}\}，其中 l≤p<q≤rl\le p\lt q\le r。
初始值：fi,i=gi,i,0=v1f_{i,i}=g_{i,i,0}=v_1，gi,i,1=0g_{i,i,1}=0，为了方便处理偶回文，令 fi+1,i=0f_{i+1,i}=0，其中 0≤i≤n0\le i\le n。
答案即为 h1,nh_{1,n}，时间复杂度为 O(n4)\mathcal{O}(n^4) ，实测可过。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn=1.5e2+10,inf=0x3f3f3f3f;
int v[maxn],f[maxn][maxn],g[maxn][maxn][maxn],h[maxn][maxn];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		int w;cin>>w;
		v[i]=(~w?w:-inf);
	}
	string s;cin>>s;s=' '+s;
	memset(f,-inf,sizeof f);
	memset(g,-inf,sizeof g);
	memset(h,-inf,sizeof h);
	for(int i=1;i<=n;i++)
		h[i][i]=max(f[i][i]=g[i][i][0]=v[1],g[i][i][1]=0);
	for(int i=0;i<=n;i++)
		h[i+1][i]=f[i+1][i]=g[i+1][i][0]=0;
	for(int len=2;len<=n;len++){
		for(int l=1,r=len;r<=n;l++,r++){
			for(int k=1;k<=len;k++){
				if(k>=2&&s[l]==s[r])
					g[l][r][k]=max(g[l][r][k],g[l+1][r-1][k-2]);
				for(int p=l;p!=r;p++){
					g[l][r][k]=max(g[l][r][k],f[l][p]+g[p+1][r][k]);
					g[l][r][k]=max(g[l][r][k],g[l][p][k]+f[p+1][r]);
				}
				f[l][r]=max(f[l][r],g[l][r][k]+v[k]);
			}
			for(int p=l;p!=r;p++)
				f[l][r]=max(f[l][r],f[l][p]+f[p+1][r]);
			h[l][r]=max(0,f[l][r]);
			g[l][r][0]=max(g[l][r][0],f[l][r]);
			for(int p=l;p<=r;p++)
				for(int q=p+1;q<=r;q++)
					h[l][r]=max(h[l][r],h[l][p]+h[q][r]);
		}
	}
	cout<<h[1][n];
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...