3027 线段覆盖 2

2018-06-17 22:43:16来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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 } 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:CPP笔记_泛型编程简单总结

下一篇:Leetcode: 2. Add Two Numbers