Codevs 3012 线段覆盖 4

3012 线段覆盖 4

时间限制: 1 s

空间限制: 64000 KB

题目等级 : 黄金 Gold

题目描述 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类型）

分类标签 Tags

二分法动态规划序列型DP

/*

DP.

f[i]表示选前i个线段的最优值.

然后DP选不选该线段.

我们保证f值单调.

然后我们从n^2优化到nlogn.

如果从前边转移的话.

按照右端点排序.

找一个合法最近的线段更新.

*/

#include<cstdio>

#include<iostream>

#include<algorithm>

#define MAXN 1000001

#define LL long long

using namespace std;

LL f[MAXN],n,tot;

struct data{LL x,y,z;}s[MAXN];

LL read()

{

    LL x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

bool cmp(const data &x,const data &y)

{

    return x.y<y.y;

}

LL erfen(LL l,LL p)

{

    LL mid,ans,r=p-1;

    while(l<=r)

    {

        mid=(l+r)>>1;

        if(s[mid].y<=s[p].x)

          ans=mid,l=mid+1;

        else r=mid-1;

    }

    return ans;

}

int main()

{

    LL x,y,z;

    n=read();

    for(int i=1;i<=n;i++)

      s[i].x=read(),s[i].y=read(),s[i].z=read();

    sort(s+1,s+n+1,cmp);

    for(int i=1;i<=n;i++)

      f[i]=max(f[i-1],f[erfen(0,i)]+s[i].z),tot=max(tot,f[i]);

    printf("%lld",tot);

    return 0;

}

/*

按照左端点排序.

从后面更新状态.

*/

#include<cstdio>

#include<iostream>

#include<algorithm>

#define MAXN 1000001

#define LL long long

using namespace std;

LL f[MAXN],n,tot;

struct data{LL x,y,z;}s[MAXN];

LL read()

{

    LL x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

bool cmp(const data &x,const data &y)

{

    return x.x<y.x;

}

LL erfen(LL p)

{

    LL mid,ans,l=p+1,r=n+1;

    while(l<=r)

    {

        mid=(l+r)>>1;

        if(s[mid].x>=s[p].y)

          ans=mid,r=mid-1;

        else l=mid+1;

    }

    return ans;

}

int main()

{

    LL x,y,z;

    n=read();

    for(int i=1;i<=n;i++)

      s[i].x=read(),s[i].y=read(),s[i].z=read();

    sort(s+1,s+n+1,cmp);

    for(int i=n;i>=1;i--)

      f[i]=max(f[i+1],f[erfen(i)]+s[i].z),tot=max(tot,f[i]);

    printf("%lld",tot);

    return 0;

}

巴特西

Codevs 3012 线段覆盖 4

最新文章

热门文章