线段覆盖4(codevs 3012)

时间:2021-09-10 08:31:13
题目描述 Description

数轴上有n条线段,线段的两端都是整数坐标,坐标范围在0~1000000,每条线段有一个价值,请从n条线段中挑出若干条线段,使得这些线段两两不覆盖(端点可以重合)且线段价值之和最大。

输入描述 Input Description

第一行一个整数n,表示有多少条线段。

接下来n行每行三个整数, ai bi ci,分别代表第i条线段的左端点ai,右端点bi(保证左端点<右端点)和价值ci。

输出描述 Output Description

输出能够获得的最大价值

样例输入 Sample Input

3

1 2 1

2 3 2

1 3 4

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

n <= 1000000

0<=ai,bi<=1000000

0<=ci<=1000000

数据输出建议使用long long类型(Pascal为int64或者qword类型)

/*
终于明白为什么用右端点排序了,因为这样排序可以保证i能接上的点一定在i的前面,就可以
找i之间的点的最大值,朴素的找法是O(n^2)的,可以考虑用二分,因为右端点具有单调性,
但是f数组不具有单调性,所以可以考虑设g[i]=max(f[j](j<i)),那么g就具有单调性了
*/
#include<cstdio>
#include<algorithm>
#include<iostream>
#define N 1000010
#define ll long long
using namespace std;
ll n,f[N],ans;
struct node
{
ll x,y,z;
};node e[N];
ll read()
{
ll num=,flag=;char c=getchar();
while(c<''||c>''){if(c=='-')flag=-;c=getchar();}
while(c>=''&&c<=''){num=num*+c-'';c=getchar();}
return num*flag;
}
bool cmp(const node&s1,const node&s2)
{
if(s1.y!=s2.y)return s1.y<s2.y;
}
ll erfen(ll l,ll r,ll x)
{
while(l<=r)
{
ll mid=(l+r)/;
if(e[mid].y<=x)l=mid+;
else r=mid-;
}
if(e[l].y<=x)return l;
return l-;
}
int main()
{
n=read();
for(ll i=;i<=n;i++)
e[i].x=read(),e[i].y=read(),e[i].z=read();
sort(e+,e+n+,cmp);
f[]=e[].z;ans=max(ans,f[]);
for(ll i=;i<=n;i++)
{
/*ll maxn=0;
for(ll j=1;j<i;j++)
if(e[j].y<=e[i].x)maxn=max(maxn,f[j]);
f[i]=maxn+e[i].z;*/
f[i]=max(f[erfen(,i,e[i].x)]+e[i].z,f[i-]);
ans=max(ans,f[i]);
}
cout<<ans;
return ;
}