编号 题目名称 状态 分数 总时间 内存 代码 提交者 提交时间
#148 #9. 消灭敌人 Accepted 100 1024 ms 2324 K C++ / 1.2 K Sengxian 2016-11-14 15:30:43
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

const int MAX_N = 300 + 3, INF = 0x3f3f3f3f;
int n, a[MAX_N], b[MAX_N], d[MAX_N], dp[MAX_N * 2][MAX_N * 2];

int compress() {
	vector<int> vs;
	for (int i = 0; i < n; ++i) {
		vs.push_back(a[i]);
		vs.push_back(b[i]);
	}
	sort(vs.begin(), vs.end());
	vs.erase(unique(vs.begin(), vs.end()), vs.end());
	for (int i = 0; i < n; ++i) {
		a[i] = lower_bound(vs.begin(), vs.end(), a[i]) - vs.begin();
		b[i] = lower_bound(vs.begin(), vs.end(), b[i]) - vs.begin();
	}
	return vs.size();
}

int main() {
	freopen("enemy.in", "r", stdin);
	freopen("enemy.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%d%d%d", a + i, b + i, d + i);
	
	int m = compress();
	for (int w = 1; w <= m; ++w)
		for (int i = 0; i + w <= m; ++i) {
			int j = i + w, mx = -1, idx = -1;
			for (int k = 0; k < n; ++k)
				if (a[k] >= i && b[k] < j && d[k] > mx) mx = d[idx = k];
			if (mx == -1) {
				dp[i][j] = 0;
				continue;
			} else dp[i][j] = INF;
			for (int k = a[idx]; k <= b[idx]; ++k)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + mx);
		}
		
	printf("%d\n", dp[0][m]);
	return 0;
}
测试点 #1
Accepted
得分:10
用时:0 ms
内存:948 KiB

输入文件

19
5 86 53
3 98 28
46 78 75
27 56 35
1 86 30
7 72 23
57 78 51
15 92 5
17 67 36
17 56 19
3 78 25
11 78 46
1 51 93
5 57 40...
期望输出
208
你的输出
208

测试点 #2
Accepted
得分:10
用时:0 ms
内存:940 KiB

输入文件

14
2 95 34
38 99 60
21 99 33
16 52 74
1 16 6
6 95 3
1 90 36
41 46 3
6 99 23
47 50 49
2 38 42
30 44 67
6 90 76
1 29 69
期望输出
192
你的输出
192

测试点 #3
Accepted
得分:10
用时:0 ms
内存:936 KiB

输入文件

15
55 79 9
11 79 63
53 74 52
36 42 87
88 89 94
74 88 57
53 60 66
36 41 51
36 79 20
60 83 64
41 75 62
22 75 16
29 83 21
3...
期望输出
247
你的输出
247

测试点 #4
Accepted
得分:10
用时:168 ms
内存:2284 KiB

输入文件

300
696 7595 5924
2227 6195 2475
2652 8974 1686
2686 7462 4428
4215 9512 5549
2295 9430 6993
3058 5290 3574
1004 7680 48...
期望输出
9993
你的输出
9993

测试点 #5
Accepted
得分:10
用时:176 ms
内存:2292 KiB

输入文件

300
920 9026 4428
494 7281 6961
4010 8499 9607
2581 6377 614
1365 8473 1078
3322 6980 340
1809 8015 270
3593 8587 3472
3...
期望输出
9985
你的输出
9985

测试点 #6
Accepted
得分:10
用时:192 ms
内存:2276 KiB

输入文件

300
779 9446 952
90 6230 8497
4689 9221 2482
17 2256 2483
3973 9914 914
1481 5890 4575
3656 8419 2034
4602 9856 3172
234...
期望输出
76401
你的输出
76401

测试点 #7
Accepted
得分:10
用时:184 ms
内存:2276 KiB

输入文件

300
66 9906 3534
7 344 6220
1368 9542 7967
4325 4729 6545
3695 8719 4365
1490 7289 3202
190 9294 2499
4049 5171 7448
258...
期望输出
92026
你的输出
92026

测试点 #8
Accepted
得分:10
用时:200 ms
内存:2276 KiB

输入文件

300
2840 6186 2856
2772 3543 4488
355 7626 4299
2494 5456 9256
7350 9987 1314
5355 7451 3799
7899 8198 7211
3208 9281 54...
期望输出
102754
你的输出
102754

测试点 #9
Accepted
得分:10
用时:52 ms
内存:2320 KiB

输入文件

300
2 5 4
4 7 7
6 9 10
8 11 13
10 13 16
12 15 19
14 17 22
16 19 25
18 21 28
20 23 31
22 25 34
24 27 37
26 29 40
28 31 43...
期望输出
68100
你的输出
68100

测试点 #10
Accepted
得分:10
用时:52 ms
内存:2324 KiB

输入文件

300
1 6000 1
11 5999 3
21 5998 5
31 5997 7
41 5996 9
51 5995 11
61 5994 13
71 5993 15
81 5992 17
91 5991 19
101 5990 21
...
期望输出
599
你的输出
599