Codeforces - Yet Another Segments Subset

题目链接：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