专栏文章

题解：CF2018D Max Plus Min Plus Size

00xyz
CF2018D题解参与者 3已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@mir1xzfw
此快照首次捕获于
2025/12/04 14:25
3 个月前
此快照最后确认于
2025/12/04 14:25
3 个月前
查看原文
一道很妙的题。动态 DP。
首先，一个很显然的想法是令 fi,j,k,0/1f_{i,j,k,0/1} 表示考虑前 ii 个数，红数最小值为 jj，红数最大值为 kk，第 ii 个数不涂/涂红时的最大红数数量。枚举前 i−1i-1 个最小值/最大值来转移，时间复杂度 O(n4)O(n^4)。
考虑优化。显然这个状态数就有很大问题，所以我们必须减少状态数量。根据数学直觉，最优解里面一定有一个染色方案染红了至少一个全局最大值。我们取任意一个染色方案，其染红的数下标集合为 SS，如果它不包含任何一个全局最大值，那么我们假设有一个全局最大值 aia_i，考虑染色集合 (S−{i−1}−{i+1})∪{i}(S-\{i-1\}-\{i+1\})\cup\{i\}，它符合不能相邻的条件，且 Δmin⁡≥0,Δmax⁡≥1,Δ size≥−1\Delta\min\ge 0,\Delta\max\ge 1,\Delta\text{ size}\ge -1，从而答案不会更小。
从而，我们可以钦定红数的 max⁡\max 就是全局最大值 mxmx。接下来，我们从大到小枚举红数的 min⁡\min，然后求出“mxmx 至少染红一个，所有小于 min⁡\min 的数均不能染红，染红的数不能相邻”情况下染红数最大个数。如果暴力做依然是 O(n2)O(n^2) 的，不行。我们考虑每次减小 min⁡\min 之后带来的影响，实际上就是一些原本必定不能染红的变成可染可不染了。我们维护每一个连通块 i:[l,r]i:[l,r]，令 fi,0/1,0/1,0/1f_{i,0/1,0/1,0/1} 表示连通块 ii 左端点 ll 不染/染，右端点 rr 不染/染，此连通块内没有/有强制将一个 mxmx 染红。那么，令 ei=max⁡{fi,∗,∗,0},hi=min⁡{ei−fi,∗,∗,1}e_i=\max\{f_{i,*,*,0}\},h_i=\min\{e_i-f_{i,*,*,1}\}，最大的染色个数就是 (∑ei)−min⁡{hi}(\sum e_i)-\min\{h_i\}。eie_i 在合并的时候直接维护即可。至于 hih_i，其实它要么是 infinf（即这个区间不存在 mxmx），要么是 0,10,1（若这个区间有 mxmx，且所有最大化染色个数的方案都不包括全局最大值 mxmx，那么一定是 l,rl,r 同奇偶，最大化染色个数的方案是将与 l,rl,r 同奇偶的所有点染色，共计 (r−l+2)/2(r-l+2)/2 个，那么我们取原本染色集合的补集就一定染了 mxmx，且染色个数仅减少了 11），所以我们开两个桶记录一下 0,10,1 的个数即可。时间复杂度 O(nα(n))O(n\alpha(n))。
为了省事，我写的代码是 O(nlog⁡n)O(n\log n) 的。
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int _=4e5+5,inf=1e9;
multiset<int>d;
int f[_][2][2][2],a[_],b[_],v[_],l[_],r[_],h[_],e[_],c,s,mx,w,n,T;
map<int,vector<int> >p;
int g(int x){
	return b[x]==x?x:b[x]=g(b[x]);
}
inline void del(int x){
	multiset<int>::iterator u=d.lower_bound(x);
	if(u!=d.end()&&(*u)==x)d.erase(u);
}
inline void mer(int x,int y){
	b[x]=b[y]=++c;l[c]=l[x];r[c]=r[y];
	del(h[x]);del(h[y]);s-=e[x];s-=e[y];
	h[c]=inf;e[c]=0;
	for(int i:{0,1})
		for(int j:{0,1})
			for(int k:{0,1})
				for(int I=0;I<2-k;I++)
					for(int J:{0,1})
						for(int K:{0,1})f[c][i][j][J|K]=max(f[c][i][j][J|K],f[x][i][k][J]+f[y][I][j][K]);
	for(int i:{0,1})
		for(int j:{0,1})e[c]=max(e[c],f[c][i][j][0]);
	for(int i:{0,1})
		for(int j:{0,1})h[c]=min(h[c],e[c]-f[c][i][j][1]);
	d.insert(h[c]);s+=e[c];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n;mx=w=s=0;c=n;p.clear();d.clear();
		for(int i=1;i<=n;i++){
			cin>>a[i];v[i]=0;
			e[i]=1;l[i]=r[i]=i;
			mx=max(mx,a[i]);
			p[-a[i]].push_back(i);
		}
		for(int i=1;i<n+n;i++){
			b[i]=i;
			for(int j:{0,1})
				for(int k:{0,1})
					for(int I:{0,1})f[i][j][k][I]=-inf;
		}
		for(int i=1;i<=n;i++)
			if(a[i]==mx){
				h[i]=0;
				for(int j:{0,1})f[i][j][j][j]=j;
				f[i][1][1][0]=1;
			}else{
				h[i]=inf;
				for(int j:{0,1})f[i][j][j][0]=j;
			}
		for(auto i:p){
			for(int j:i.second){
				d.insert(h[j]);s+=e[j];
				if(j>1&&v[j-1])mer(g(j-1),g(j));
				if(j<n&&v[j+1])mer(g(j),g(j+1));
				v[j]=1;
			}
			w=max(w,mx-i.first+s-*d.begin());
		}
		cout<<w<<'\n';
	} 
	return 0;
}

评论

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

正在加载评论...