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