Summary:
1. Fill dp array explicitly by using dp[i] = dp[i+1]
2. At time i, do the first job explicitly
Code:
|
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72 |
/* * source.cpp * * Created on: Apr 5, 2014 * Author: sangs */#include <iostream>#include <stdio.h>#include <set>#include <memory.h>#include <vector>using
namespace std;class
Job {public: int
st, ed, duration; Job(int
_st, int
_ed, int
_du):st(_st), ed(_ed), duration(_du) {} Job() { st = ed = duration = 0; }};vector<Job> jobs[2500];int
dp[2500];int
cal(int
n) { memset(dp, 0, sizeof(dp)); for(int
i = n; i >= 0; i --) { if(jobs[i].size() == 0) { dp[i] = dp[i+1]; continue; } int
du = jobs[i][0].duration; dp[i] = du + dp[i+du]; for(size_t j = 1; j < jobs[i].size(); j ++) { du = jobs[i][j].duration; dp[i] = min(dp[i], du+dp[i+du]); } } for(int
i = 0; i <= n; i ++) jobs[i].clear(); return
dp[0];}int
main() { freopen("input.txt", "r", stdin); int
cases, m; scanf("%d", &cases); while(cases --) { scanf("%d", &m); int
n = 0; for(int
i = 0; i < m; i ++) { int
st, ed, du; scanf("%d%d%d", &du, &st, &ed); n = max(n, ed); for(int
j = st; j <= ed-du; j ++) { jobs[j].push_back(Job(st, ed, du)); } } int
res = cal(n); printf("%d\n", res); } return
0;} |
POJ 1337 A Lazy Worker,布布扣,bubuko.com
原文：http://www.cnblogs.com/zhouzhuo/p/3647657.html