首页 > 代码库 > CODEVS3037 线段覆盖 5[序列DP 二分]

CODEVS3037 线段覆盖 5[序列DP 二分]

2024-08-17 00:09:16   217人阅读

3037 线段覆盖 5 

 

 时间限制: 3 s 
 空间限制: 256000 KB 
 题目等级 : 钻石 Diamond
 
 
 
题目描述 Description

数轴上有n条线段，线段的两端都是整数坐标，坐标范围在0~10^18，每条线段有一个价值，请从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<=10^18

0<=ci<=10^9

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

 

也是按r排序

一开始想f[i]表示以i为最后一个线段的最大价值

然后并不好二分

发现其实f[i]表示前i个点最大价值就可以

f[i]=max(f[i-1],f[Bin(i)]+a[i].w)

二分时还是找最靠右的符合要求的区间i，不会丢解

 

////  main.cpp//  codevs3012////  Created by Candy on 10/17/16.//  Copyright © 2016 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const int N=1e6+5;inline ll read(){    char c=getchar();ll x=0,f=1;    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}    return x*f;}int n;struct seg{    ll l,r,w;    bool operator <(const seg &x)const{return r<x.r;}}a[N];ll f[N];int Bin(int x){    int l=1,r=x-1,m,ans=0;    while(l<=r){        m=(l+r)/2;        if(a[m].r<=a[x].l) ans=m,l=m+1;        else r=m-1;    }    return ans;}void dp(){    for(int i=1;i<=n;i++)        f[i]=max(f[i-1],f[Bin(i)]+a[i].w);}int main(int argc, const char * argv[]) {    n=read();    for(int i=1;i<=n;i++){        a[i].l=read(),a[i].r=read();a[i].w=read();        //if(a[i].l>a[i].r) swap(a[i].l,a[i].r);    }    sort(a+1,a+1+n);    dp();    printf("%lld",f[n]);    return 0;}

 

CODEVS3037 线段覆盖 5[序列DP 二分]


联系
我们