codevs 3095 黑心的市长

3095 黑心的市长

时间限制: 1 s

空间限制: 32000 KB

题目等级 : 钻石 Diamond

题目描述 Description

A市有一条长Nkm的高速公路。有M个人各自想承包下a~b的路段。

这不给点钱是不行的，每人给ci元。

市长很黑心，想赚很多钱。如果同时允许多人承包同一路段，是不行的。

求市长最多赚多少钱。

输入描述 Input Description

正整数N M

M行，ai，bi，ci。

输出描述 Output Description

钱数

样例输入 Sample Input

10 3

1 5 10

4 7 9

7 10 8

样例输出 Sample Output

数据范围及提示 Data Size & Hint

M《=500，N《=1014，ci《=109.

【题目大意】每一条线段都有一定的价值，求线段两两不覆盖能得到的最大价值。

【思路】序列dp 不能是越多线段越好，要求价值最大。f[i]为前i条线段能获得的最大值。最后 max{f[i---m]}

【code】

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

long long n,m,ans,f[];

struct E

{

    long long x,y,v;

}s[];

bool cmp(E a,E b)

{

    return a.y<b.y;

}

int read()

{

    long long f=,x=;char ch=getchar();

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

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return f*x;

}

int main()

{

    n=read();m=read();

    for(int i=;i<=m;i++)

    {

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

    }

    sort(s+,s+m+,cmp);

    for(int i=;i<=m;i++)

    for(int j=;j<i;j++)

    if(s[i].x>=s[j].y)

    f[i]=max(f[j]+s[i].v,f[i]);

    for(int i=;i<=m;i++)

    ans=max(ans,f[i]);

    printf("%d\n",ans);

    return ;

}

//f[1--m] 1       30      67      91      101     100

巴特西

codevs 3095 黑心的市长

3095 黑心的市长

最新文章

热门文章