欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Codeforces - Yet Another Segments Subset

程序员文章站 2022-03-11 11:57:42
题目链接:Yet Another Segments Subset考虑区间dp,dp[i][j] 为区间 [ i , j ] 的最大价值。然后对于区间的合并:dp[i][j] = max{dp[i][k]+dp[k+1][j]},如果每次都考虑显然复杂度为:O(n^3),无法通过此题。但是我们可以发现如果当前存在某条线段才需要考虑切割,否则在之前已经被考虑过,故可以优化到O(n^2)然后线段值域很大,可以离散化。AC代码:#pragma GCC optimize("-Ofast","-fu...

题目链接:Yet Another Segments Subset


考虑区间dp,dp[i][j] 为区间 [ i , j ] 的最大价值。

然后对于区间的合并:dp[i][j] = max{dp[i][k]+dp[k+1][j]},如果每次都考虑显然复杂度为:O(n^3),无法通过此题。
但是我们可以发现如果当前存在某条线段和区间边界有交点,才需要考虑切割,否则在之前已经被考虑过,故可以优化到O(n^2)

然后线段值域很大,可以离散化。

AC代码:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=6e3+10;
int dp[N][N],l[N],r[N],n,m; bool vis[N][N];
vector<int> v,vec[N];
inline int get(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
void solve(){
	cin>>n; v.clear();
	for(int i=1;i<=n;i++)	cin>>l[i]>>r[i],v.push_back(l[i]),v.push_back(r[i]);
	sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end()); m=v.size();
	for(int i=1;i<=m;i++)	for(int	j=1;j<=m;j++)	vis[i][j]=dp[i][j]=0;
	for(int i=1;i<=m;i++)	vec[i].clear();
	for(int i=1;i<=n;i++)	vis[l[i]=get(l[i])][r[i]=get(r[i])]=1;
	for(int i=1;i<=n;i++)	vec[l[i]].push_back(r[i]);
	for(int L=1;L<=m;L++){
		for(int i=1;i+L-1<=m;i++){
			int j=i+L-1;
			dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
			for(int k:vec[i])	if(k<=j)	dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
			dp[i][j]+=vis[i][j];
		}
	}
	cout<<dp[1][m]<<'\n';
}
signed main(){
	int T; cin>>T; while(T--) solve();
	return 0;
}

本文地址:https://blog.csdn.net/weixin_43826249/article/details/107866116