https://codeforces.com/contest/1106/problem/E

题意：1到 n 的时间轴上，给定 k 个区间，每个有 d 值和 w 值，当位于坐标 x 时，可以会选择包含 x 的区间中 w 值最大，若 w 相同，则选 d 值最大，若还相同，则随机选一个。获得区间的 w 值，并移动到 d 值去。可以选择 m 个点堵住，在被堵住的点处不能获得 w 和移动。问最少获得的 w 值之和。

扫描线+dp

dp[i][j]dp[i][j] 表示在坐标 i，总共堵了 j 个点，最小 w 值和。

有两种转移：不堵坐标 i，则获得 w 值，并移动到坐标 i 对应区间的 d 值去。堵坐标 i ，则什么都不加，并移动到 i+1 去。

由于需要知道移动到后面某个坐标的 dp 值，所以这里从后往前转移更好。先算出后面的dp值，再算前面的。

扫描线确定每个坐标应该选择的区间，并记录 w 值和 d 值。

注意 multiset erase key 会删除所有为 key 的元素，所以会导致某些不应该被删除的元素提前删除了。要只删除一个可以 erase(find())。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
int n, m, k;
int S[N], T[N], D[N];
ll W[N];
int d[N];
ll w[N];
struct X
{
	int p, d;
	ll op;
	bool operator<(const X& b)const {
		return p == b.p ? op > b.op:p < b.p;
	}
};
vector<X>vc;
typedef pair<ll, int>pii;
multiset<pii, greater<pii> >st;
ll dp[N][210];
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= k; i++)scanf("%d%d%d%lld", &S[i], &T[i], &D[i], &W[i]);
	for (int i = 1; i <= k; i++) {
		vc.push_back(X{ S[i],D[i],W[i] });
		vc.push_back(X{ T[i] + 1,D[i],-W[i] });
	}
	sort(vc.begin(), vc.end());
	for (int i = 1, p = 0; i <= n; i++) {
		while (p < (int)vc.size() && vc[p].p <= i) {
			if (vc[p].op > 0)st.insert({ vc[p].op,vc[p].d });
			else st.erase(st.find({ -vc[p].op,vc[p].d }));
			p++;
		}
		if (st.empty()) {
			w[i] = 0;
			d[i] = i;
		}
		else {
			pii tp = *st.begin();
			w[i] = tp.first;
			d[i] = tp.second;
		}
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[n + 1][0] = 0;
	for (int i = n; i >= 1; i--) {
		for (int j = 0; j <= m; j++) {
			dp[i][j] = dp[d[i] + 1][j] + w[i];
			if (j > 0)dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
		}
	}
	ll ans = inf;
	for (int i = 0; i <= m; i++)ans = min(ans, dp[1][i]);
	printf("%lld\n", ans);
	return 0;
}