3027 线段覆盖 2

3027 线段覆盖 2

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

题解

 查看运行结果

题目描述 Description

数轴上有n条线段,线段的两端都是整数坐标,坐标范围在0~1000000,每条线段有一个价值,请从n条线段中挑出若干条线段,使得这些线段两两不覆盖(端点可以重合)且线段价值之和最大。

n<=1000

输入描述 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

数据范围

对于40%的数据,n≤10;

对于100%的数据,n≤1000;

0<=ai,bi<=1000000

0<=ci<=1000000

思路:首先我们按照正常线段覆盖问题的方法把所有线段按照结束顺序排序

   然后我们想,对于每一个线段,我们有选和不选两种情况

   so我们遍历所有节点,如果该节点能被访问,并且该节点贮存数组中的最大值加上我们正在dp的点的值大于原来的值。我们就更改

   这样dp下来

   dp[n]中的就是最大值

   动态转移方程:

dp[i]=max(dp[i],dp[p]+a[i].v)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 const int MAXN=1001;
 6 struct node
 7 {
 8     int bg;
 9     int ed;
10     int v;
11 }a[MAXN];
12 int comp(const node &a ,const node &b)
13 {
14     return a.ed<b.ed;
15 }
16 int dp[MAXN];
17 int main()
18 {
19     int n;
20     scanf("%d",&n);
21     for(int i=1;i<=n;i++)
22     {
23         int x,y,z;
24         scanf("%d%d%d",&x,&y,&z);
25         if(x>y)swap(x,y);
26         a[i].bg=x;a[i].ed=y;a[i].v=z;
27     }
28     sort(a+1,a+n+1,comp);
29     for(int i=1;i<=n;i++)
30     {
31         dp[i]=max(dp[i-1],a[i].v);
32         for(int p=i-1;p>=1;p--)
33         {
34             if(a[p].ed<=a[i].bg)
35             dp[i]=max(dp[i],dp[p]+a[i].v);
36         }
37     }
38     printf("%d",dp[n]);
39     return 0;
40 } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏测试开发架构之路

C语言之位运算

指针和位运算很适合编写系统软件的需要。 位运算指进行二进制位的运算。   按位与”运算符 & 用途 1)清零 2)取一个数中某些指定位(比如只需要低8位) 3)...

43310
来自专栏小樱的经验随笔

洛谷 P1598 垂直柱状图【字符串+模拟】

P1598 垂直柱状图 题目描述 写一个程序从输入文件中去读取四行大写字母(全都是大写的,每行不超过72个字符),然后用柱状图输出每个字符在输入文件中出现的次数...

3115
来自专栏数据结构与算法

洛谷P2870 [USACO07DEC]最佳牛线,黄金Best Cow Line, Gold

题目描述 FJ is about to take his N (1 ≤ N ≤ 30,000) cows to the annual"Farmer of the...

2775
来自专栏机器学习入门

挑战程序竞赛系列(86):3.6极限情况(3)

挑战程序竞赛系列(86):3.6极限情况(3) 传送门:AOJ 2201: Immortal Jewels 翻译参考至hankcs: http://www....

21910
来自专栏GreenLeaves

C# String.Format的格式限定符与Format方法将多个对象格式化一个字符串原理

Format方法将多个对象格式化成一个字符串Format方法解析格式字符串的原理:

1162
来自专栏HansBug's Lab

2431: [HAOI2009]逆序对数列

2431: [HAOI2009]逆序对数列 Time Limit: 5 Sec  Memory Limit: 128 MB Submit: 954  Solv...

2896
来自专栏wannshan(javaer,RPC)

dubbo序列化过程源码分析

先看下dubbo在serialize层的类设计方案 序列化方案的入口,是接口Serialization的实现类。 /** * Serialization. ...

8649
来自专栏数据之美

Python Tips, Tricks, and Hacks

一、快速技巧 1.1、4 种引号 '  '''  "  """  print """I wish that I'd never heard him say...

2735
来自专栏一个会写诗的程序员的博客

《Kotlin极简教程》第五章 Kotlin面向对象编程(OOP)一个OOP版本的HelloWorld构造函数传参Data Class定义接口&实现之写pojo bean定一个Rectangle对象封

We frequently create a class to do nothing but hold data. In such a class some s...

2184
来自专栏mySoul

设计模式 里氏替换原则

在场景中,三毛需要什么枪支,就直接new 出一个枪支即可,然后其内通过抽象类获取到对象,然后对齐进行修饰

1246

扫码关注云+社区

领取腾讯云代金券