题目传送门(BZOJ)

题解 :

国家集训队论文
我们模拟一下论文给出的解题过程 qwq(
贪心的完成收益大的任务,
由于一个任务只占一个时间点, 我们看一下要完成当前这个任务会不会影响之前的某个任务,
如果可以不影响, 那么把那个时间点给它, 然后继续, 否则为了选这个而顶掉之前的一定不优
这是一个二分图匹配的东西, 但是时间点集过于庞大, 可能用到的却有限, 所以只要留下有用的
(关于选整个点集在最优策略上等同于选有用点集的证明, 请参考论文附录
先将所有左端点排序, 维护一个集合 val 表示时间点,
val[i] 至少是 val[i-1]+1, 并且要到 任务iS
然后维护一个指针, 把每个区间的时间点初始化好(最左的可能时间点)
然后按任务价值排序, 从大到小贪心匹配即可
直接匈牙利的复杂度是不对的, 但是本题有一个优化 :
对于当前要给 i 让位的 fr[y], 如果它的 t 要小于 it, 那就把 i 向后尝试一位
由于 y 之前的时间点已经尝试过了/不符合时间要求, 所以直接从 y+1 继续尝试就好
复杂度 O(N^2)

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 5100;struct MISSION { int s, t, v;}a[N];bool cmps(const MISSION &A, const MISSION &B) { return A.s < B.s;}bool cmpv(const MISSION &A, const MISSION &B) { return A.v > B.v;}int n, val[N], fr[N];bool find(int x, int y) { if(val[y] > a[x].t) return 0; if(!fr[y]) return fr[y] = x, 1; if(a[fr[y]].t < a[x].t) return find(x, y+1); if(find(fr[y], y+1)) { fr[y] = x; return 1; } return 0;}int main() { scanf("%d", &n); for(int i = 1; i <= n; i ++ ) scanf("%d%d%d", &a[i].s, &a[i].t, &a[i].v); sort(a+1, a+n+1, cmps); for(int i = 1; i <= n; i ++ ) val[i] = max(val[i-1]+1, a[i].s); for(int i = 1, j = 1; i <= n; i ++ ) { while(j < n && val[j] < a[i].s) j ++ ; a[i].s = j; } sort(a+1, a+n+1, cmpv); long long ans = 0; for(int i = 1; i <= n; i ++ ) if(find(i, a[i].s)) { ans += a[i].v; } printf("%lld\n", ans); return 0;}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<