带权区间调度问题,软件的期中复习

Posted by Cww97 on 2017-11-16

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/78546557
这里写图片描述

poj3616

对end_time排序,然后dp

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
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e3 + 7;
const int INF = 0x3f3f3f3f;
int f[N];
struct job{
int s, t, w;
inline void read(){
scanf("%d%d%d", &s, &t, &w);
}
bool operator < (const job &b) const {
return t < b.t;
}
} jobs[N];

int Search(int l, int r, const int &val){
for (; l < r;){
int mid = (l + r) >> 1;
if (jobs[mid].t <= val) l = mid + 1;
else r = mid;
}
return l;
}

int main(){
//freopen("in.txt", "r", stdin);
for (int n, m, r; ~scanf("%d%d%d", &n, &m, &r);){
jobs[0].t = -INF;
for (int i = 1; i <= m; i++){
jobs[i].read();
}
sort(jobs + 1, jobs + m+1); // sort by end time

f[0] = 0; // dp
for (int i = 1; i <= m; i++){
//idx is the earliest overlap job
int idx = Search(0, i, jobs[i].s - r);
f[i] = max(f[i-1], f[idx-1] + jobs[i].w);
}
printf("%d\n", f[m]);
}
return 0;
}

这个伪代码,是假的

这里写图片描述
这里写图片描述