首页 > > 程序设计 > C/C++ >

3027 线段覆盖 2

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

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

1 2 1

2 3 2

1 3 4

样例输出 Sample Output

数据范围及提示 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 }