背景
你知道吗，SQ Class的人都很喜欢打CS。（不知道CS是什么的人不用参加这次比赛）。
描述
今天，他们在打一张叫DUSTII的地图，万恶的*要炸掉藏在A区的SQC论坛服务器！我们SQC的人誓死不屈，即将于*展开激战，准备让一个人守着A区，这样*就不能炸掉服务器了。（一个人就能守住??这人是机械战警还是霹雳游侠？）
但是问题随之出现了，由于DustII中风景秀丽，而且不收门票，所以n名反恐精英们很喜欢在这里散步，喝茶。他们不愿意去单独守在荒无人烟的A区，在指挥官的一再命令下，他们终于妥协了，但是他们每个人都要求能继续旅游，于是给出了自己的空闲时间，而且你强大的情报系统告诉了你恐怖份子计划的进攻时间（从s时刻到e时刻）。
当然，精明的SQC成员不会为你免费服务，他们还要收取一定的佣金（注意，只要你聘用这个队员，不论他的执勤时间多少，都要付所有被要求的佣金）。身为指挥官的你，看看口袋里不多的资金（上头真抠！），需要安排一个计划，雇佣一些队员，让他们在保证在进攻时间里每时每刻都有人员执勤，花费的最少资金。
格式
输入格式
第一行是三个整数n(1≤n≤10000)，s和e（1≤s≤e≤90000）。
接下来n行，描述每个反恐队员的信息：空闲的时间si, ei（1≤si≤ei≤90000）和佣金ci（1≤ci≤300000）。
输出格式
一个整数，最少需支付的佣金，如果无解，输出“-1”。
样例1
样例输入1
3 1 5
1 3 3
4 5 2
1 1 1
样例输出1
5
限制
提示
敌人从1时刻到4时刻要来进攻，一共有3名反恐队员。第1名从1时刻到3时刻有空，要3元钱（买糖都不够??）。以此类推。
一共要付5元钱，选用第1名和第2名。
来源
SQ CLASS公开编程竞赛2008——Problem D
Source: WindTalker, liuichou, royZhang
题目大意
数轴上有一些区间，每个区间有一个费用。要求选择一些区间将$[s, t]$覆盖，问最小的总费用。
Solution#1 Dynamic Programming & Heap Optimization
dp是显然的。 用$f[i]$表示将$[s, i]$覆盖的最小费用。
考虑转移。显然通过能够覆盖点$i$的线段进行转移，因此有
$f[i] = \max_{线段j能覆盖点i}\left\{ f[l_{j} - 1] + w_{j}\right\}$
显然可以用一个堆维护右边的那一坨。
Code
/**
* Vijos
* Problem#1404
* Accepted
* Time: 98ms
* Memory: 3.48m
*/
#include <bits/stdc++.h>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean; #define ll long long typedef class Segment {
public:
int l, r;
int w; Segment(int l = , int r = , int w = ):l(l), r(r), w(w) { } boolean operator < (Segment b) const {
return l < b.l;
}
}Segment; typedef class Heap {
public:
priority_queue<ll, vector<int>, greater<int> > que;
priority_queue<ll, vector<int>, greater<int> > del; Heap() { } ll top() {
while (!del.empty() && que.top() == del.top())
que.pop(), del.pop();
return que.top();
} void push(ll x) {
que.push(x);
} void remove(ll x) {
del.push(x);
} boolean empty() {
return (que.size() == del.size());
}
}Heap; int n, s, t;
Segment* ss;
vector<Segment*> *g;
Heap h;
ll *f; inline void init() {
scanf("%d%d%d", &n, &s, &t);
ss = new Segment[(n + )];
g = new vector<Segment*>[(t - s + )];
f = new ll[(t - s + )];
t = t - s + ;
for (int i = ; i <= n; i++) {
scanf("%d%d%d", &ss[i].l, &ss[i].r, &ss[i].w);
ss[i].l = max(ss[i].l - s, ) + ;
ss[i].r = max(ss[i].r - s, ) + ;
if (ss[i].r > t) ss[i].r = t;
}
} inline void solve() {
int p = ;
f[] = ;
sort (ss + , ss + n + );
for (int i = ; i <= t; i++) {
while (p <= n && ss[p].l == i) {
h.push(f[ss[p].l - ] + ss[p].w);
g[ss[p].r].push_back(ss + p);
p++;
}
if (h.empty()) {
puts("-1");
return;
}
f[i] = h.top();
for (int j = ; j < (signed)g[i].size(); j++)
h.remove(f[g[i][j]->l - ] + g[i][j]->w);
g[i].clear();
}
printf(Auto"\n", f[t]);
} int main() {
init();
solve();
return ;
}
Solution 1
Solution#2 Shortest Path & Segment Tree Optimization
其实把dp的转移变成边，然后发现巧的是每条区间的前一个点，向区间上的所有整点连边。
于是写个线段树建图优化（其实没什么高端的，就是建虚点，防止重复的连边，然后再加点连边的技巧就好了）。
Code
/**
* Vijos
* Problem#1404
* Accepted
* Time: 606ms
* Memory: 16.0m
*/
#include <bits/stdc++.h>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean; #define ll long long
#define pii pair<int, int>
#define fi first
#define sc second const signed ll llf = (signed ll) (~0ull >> ); int n, s, t;
vector<pii> *g;
ll *f;
boolean *vis; inline void init() {
scanf("%d%d%d", &n, &s, &t);
t = t - s + ;
int siz = ((t + ) << ) + ;
g = new vector<pii>[siz];
f = new ll[siz];
vis = new boolean[siz];
fill(vis, vis + siz, false);
fill(f, f + siz, llf >> );
} void build(int p, int l, int r) {
if (l == r) return;
int mid = (l + r) >> ;
g[p].push_back(pii(p << , ));
g[p].push_back(pii((p << ) | , ));
build(p << , l, mid);
build((p << ) | , mid + , r);
} int query(int p, int l, int r, int idx) {
if (l == r)
return p;
int mid = (l + r) >> ;
if (idx <= mid)
return query(p << , l, mid, idx);
return query((p << ) | , mid + , r, idx);
} void query(int p, int l, int r, int ql, int qr, int st, int w) {
if (l == ql && r == qr) {
g[st].push_back(pii(p, w));
return;
}
int mid = (l + r) >> ;
if (qr <= mid)
query(p << , l, mid, ql, qr, st, w);
else if (ql > mid)
query((p << ) | , mid + , r, ql, qr, st, w);
else {
query(p << , l, mid, ql, mid, st, w);
query((p << ) | , mid + , r, mid + , qr, st, w);
}
} inline void build() {
build(, , t);
for (int i = , l, r, w; i <= n; i++) {
scanf("%d%d%d", &l, &r, &w);
l = max(l - s, ) + ;
r = max(r - s, ) + ;
if (r > t) r = t;
int id = query(, , t, l - );
query(, , t, l, r, id, w);
}
} queue<int> que;
inline void spfa(int s) {
que.push(s);
f[s] = ;
while (!que.empty()) {
int e = que.front();
que.pop();
vis[e] = false;
for (int i = ; i < (signed)g[e].size(); i++) {
int eu = g[e][i].fi, w = g[e][i].sc;
if (f[e] + w < f[eu]) {
f[eu] = f[e] + w;
if (!vis[eu]) {
vis[eu] = true;
que.push(eu);
}
}
}
}
} inline void solve() {
int is = query(, , t, );
int it = query(, , t, t);
spfa(is);
if (f[it] == (llf >> ))
puts("-1");
else
printf(Auto"\n", f[it]);
} int main() {
init();
build();
solve();
return ;
}
Solution 2
Solution#3 Shortest Path
wtf？纯最短路？没逗我？
每个区间的前一个点向区间结束点连边。然后每个点向它的前一个点连边，权值为0。
（神奇的建图方法。。）
看起来非常朴素，竟然没有dp快
Code
/**
* Vijos
* Problem#1404
* Accepted
* Time: 285ms
* Memory: 5.75m
*/
#include <bits/stdc++.h>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean; #define ll long long
#define pii pair<int, int>
#define fi first
#define sc second const signed ll llf = (signed ll) (~0ull >> ); int n, s, t;
vector<pii> *g;
ll *f;
boolean *vis; inline void init() {
scanf("%d%d%d", &n, &s, &t);
t = t - s + ;
g = new vector<pii>[t + ];
f = new ll[t + ];
vis = new boolean[t + ];
fill(vis, vis + t + , false);
fill(f, f + t + , llf >> );
} inline void build() {
for (int i = , l, r, w; i <= n; i++) {
scanf("%d%d%d", &l, &r, &w);
l = max(l - s, ) + ;
r = max(r - s, ) + ;
if (r > t) r = t;
g[l - ].push_back(pii(r, w));
}
for (int i = ; i <= t; i++)
g[i].push_back(pii(i - , ));
} queue<int> que;
inline void spfa(int s) {
que.push(s);
f[s] = ;
while (!que.empty()) {
int e = que.front();
que.pop();
vis[e] = false;
for (int i = ; i < (signed)g[e].size(); i++) {
int eu = g[e][i].fi, w = g[e][i].sc;
if (f[e] + w < f[eu]) {
f[eu] = f[e] + w;
if (!vis[eu]) {
vis[eu] = true;
que.push(eu);
}
}
}
}
} inline void solve() {
spfa();
if (f[t] == (llf >> ))
puts("-1");
else
printf(Auto"\n", f[t]);
} int main() {
init();
build();
solve();
return ;
}