全re,求调
查看原帖
全re,求调
466909
Lijinghao168楼主2024/7/28 11:21
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=150005;
int n,dp[maxn];
struct node{
	int x,y,v;
}a[maxn];
bool cmp(node x,node y){
	return x.y<y.y;
}
int erfen(int l,int r,int x){
	int ans;
	while(l<=r){
		int mid=(l+r)>>1;
		if(a[mid].y<x)ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y,a[i].v=a[i].y-a[i].x+1;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		dp[i]=max(dp[i-1],dp[erfen(1,i-1,a[i].x)]+a[i].v);
	}
	cout<<dp[n];
	
	return 0;
}
2024/7/28 11:21
加载中...