codevs 3012 线段覆盖 4 & 3037 线段覆盖 5

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类型）

分类标签 Tags 点此展开 

 

动态规划 序列型DP 离散化

AC代码：

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
inline const ll read(){
    register ll x=0,f=1;
    register char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
const int N=1e6+10;
struct node{
    ll a,b,c;
    bool operator < (const node t) const {
        return b<t.b;
    }
}s[N];int n;
ll v[N],f[N];
int find(int x){
    int l=0,r=n,mid,ans;
    while(l<=r){
        mid=l+r>>1;
        if(s[mid].b<=x) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) s[i].a=read(),s[i].b=read(),s[i].c=read();
    stable_sort(s+1,s+n+1);
    for(int i=1,pos;i<=n;i++){
        pos=find(s[i].a);
        f[i]=v[pos]+s[i].c;
        v[i]=max(v[i-1],f[i]);
    }
    printf("%lld",v[n]);
    return 0;
}