家人们 救命!!
查看原帖
家人们 救命!!
651774
illusion2019827楼主2022/11/15 16:45

家人们,我不开02优化第三个样例过不了,开02就过了,家人们能讲解一下吗 这是代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 150010;

const ll NN = 3*1000000+10;

ll f[NN];

struct seg{
	
	ll l;
	
	ll r;
	
	ll s;
	
}a[N];

bool cmp(const seg &x , const seg &y){
	return x.l<y.l;
}

int main()
{
	
	ll t;
	
	cin>>t;
	
	ll n = 0;
	
	for(int i = 1 ; i <= t ; i++)
	{
		
		int x , y;
		
		scanf("%d%d" , &x,&y);
		
		a[i].l = x;
		
		a[i].r = y;
		
		a[i].s = y-x+1;
		
		n = max(n , a[i].r);
		
	}

	sort(a+1 , a+t+1 , cmp);

	for(int i = 1 ; i <= t;  i++)
	{
		
		for(int j = a[i].r ; j <= n ; j++)
		{
			if(f[j]<f[a[i].l - 1] + a[i].s)
			{
			    f[j] = max(f[j] , f[a[i].l - 1] + a[i].s);
			}
			else
			break;
		}
		
	}
	
	cout<<f[n];

}
2022/11/15 16:45
加载中...