首页 > 代码库 > codevs 3095 黑心的市长
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
18
数据范围及提示 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[520]; struct E { long long x,y,v; }s[520]; bool cmp(E a,E b) { return a.y<b.y; } int read() { long long f=1,x=0;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return f*x; } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { s[i].x=read();s[i].y=read();s[i].v=read(); } sort(s+1,s+m+1,cmp); for(int i=1;i<=m;i++) for(int j=0;j<i;j++) if(s[i].x>=s[j].y) f[i]=max(f[j]+s[i].v,f[i]); for(int i=1;i<=m;i++) ans=max(ans,f[i]); printf("%d\n",ans); return 0; } //f[1--m] 1 30 67 91 101 100
codevs 3095 黑心的市长
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。