「codevs3027」序列DP

发表于 | 分类于

题目链接

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

n<=1000

输入描述 Input Description

第一行一个整数n，表示有多少条线段。

接下来n行每行三个整数, ai bi ci，分别代表第i条线段的左端点ai，右端点bi（保证左端点<右端点）和价值ci。

输出描述 Output Description
输出能够获得的最大价值

样例输入 Sample Input

1
2
3
4
5
6
7
8
3
1 2 1
2 3 2
1 3 4

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

1
2
3
4
5
6
7
对于40%的数据，n≤10；
对于100%的数据，n≤1000；
0<=ai,bi<=1000000
0<=ci<=1000000

首先对这道题展开分析，可以看出这是一道DP题，但是我们怎么做呢？我们首先建立一个结构体将每条线段的左端点和右端点及价值储存，按照右端点进行sort操作（用来保证左边尽可能持有更多的边）； 建立一个数组f[i],用来储存到
编号为i的这条边我们所拥有的最大价值；遍历求出发f[i]，然后max函数找到最大值；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <algorithm>
#define max(x, y) ((x) > (y) ? (x) : (y))
//这里将x，y单独加括号的原因是防止三目运算时参数x或y传的是一个式子；
using namespace std;
int n, sum, f[1000 + 5];
inline int read() {
	char ch = getchar(); int flag = 1; int res = 0;
	while(ch > '9' || ch < '0') {if(ch == '-') flag = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {res = res * 10 + ch - '0'; ch = getchar();}
	return (res * flag);
}//快读（高天宇） 只能读数，不可读字符
struct Line {
	int l, r, c;
	Line(int l = 0, int r = 0, int c = 0) : l(l), r(r), c(c) {}
}line[1000 + 5];
inline bool cmp(Line a, Line b) {
	return a.r < b.r;
}
int main() {
	n = read();
	for(int i = 1; i <= n; i++) {
		line[i].l = read();
		line[i].r = read();
		line[i].c = read();
	}
	sort(line + 1, line + n + 1, cmp);
	for(int i = 1;  i <= n; i++) f[i] = line[i].c;
    //赋值操作一定要加在sort之后； 因为sort会改变line[i].c的位置；
	for(int i = 2; i <= n; i ++) {
		for(int j = 1; j <= i - 1; j++) {
			if(line[j].r <= line[i].l) {
				f[i] = max(f[i], f[j] + line[i].c);//转移方程
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		sum = max(sum, f[i]);
	}
	printf("%d", sum);
	return 0;
}