首页 > 代码库 > 线段覆盖4（codevs 3012）
线段覆盖4（codevs 3012）
题目描述 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类型）
/* 二分+DP 还是不大懂为什么要用右端点排序 我觉得按左端点排序能保证f值小的在前面，然后不对…… 貌似还有线段树的做法 */#include<cstdio>#include<iostream>#include<queue>#include<algorithm>#define N 1000010#define ll unsigned long longusing namespace std;int n;ll f[N];struct node{ ll a,b,v;};node e[N];ll read(){ ll num=0,flag=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)flag=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*flag;}bool cmp(const node&s1,const node&s2){ return s1.b<s2.b;}int find(int x){ int l=0,r=x-1,eee; while(l<=r) { int mid=(l+r)/2; if(e[mid].b<=e[x].a) { l=mid+1; eee=mid; } else r=mid-1; } return eee;}int main(){ freopen("jh.in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) e[i].a=read(),e[i].b=read(),e[i].v=read(); sort(e+1,e+n+1,cmp); ll ans=0; for(int i=1;i<=n;i++) f[i]=max(f[i-1],f[find(i)]+e[i].v),ans=max(ans,f[i]); cout<<ans; return 0;}
线段覆盖4（codevs 3012）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。