91分TLE求助
查看原帖
91分TLE求助
732004
Lok2c210楼主2023/8/10 16:46
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
const int N=150010;
const int M=3e6+10;
class node
{
	public:
		int st,en;
};
node e[N];
int dp[M],lower[M];
int n,m;
bool cmp(node a,node b)
{
	return a.en<b.en;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&e[i].st,&e[i].en);
		lower[e[i].en]++;
		m=max(m,e[i].en);
	}
	sort(e+1,e+n+1,cmp);
	for(int i=1;i<=m;i++)
	{
		lower[i]+=lower[i-1];
	}
	
	dp[e[1].en]=e[1].en-e[1].st+1;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=lower[e[i].en];j++)
		{
			dp[e[i].en]=max(dp[e[i].en],dp[e[lower[e[j].st-1]].en]+e[j].en-e[j].st+1);
		}
	}
	printf("%d",dp[m]);
}
2023/8/10 16:46
加载中...