求助,WA#3
查看原帖
求助,WA#3
1100122
yiluntaiyang楼主2024/10/13 21:34
#include<bits/stdc++.h>
using namespace std;
const int M=1e7;
struct cowww{
	int x;
	int y;
	int length;
}a[M];
int t=1;
long long int dp[M];
bool cmp(cowww i,cowww j)
{
	return i.x<j.x;
}
int N;
int main()
{
	cin>>N;
	int maxy=0;
	for(int i=1;i<=N;++i)
	{
		cin>>a[i].x>>a[i].y;
		a[i].length=a[i].y-a[i].x+1;
		maxy=max(maxy,a[i].y);
	}
	sort(a+1,a+1+N,cmp);
	for(int i=1;i<=maxy;++i)
	{
		if(a[t].x==i)
		{
			dp[a[t].y]=max(dp[a[t].y],dp[a[t].x-1]+a[t].length);
			t++;
		}
		dp[i]=max(dp[i],dp[i-1]);
	}	
	cout<<dp[maxy]<<" ";
	return 0;
}
2024/10/13 21:34
加载中...