首页 > 代码库 > BZOJ 2034 【2009国家集训队】 最大收益
BZOJ 2034 【2009国家集训队】 最大收益
Description
给出$N$件单位时间任务，对于第$i$件任务，如果要完成该任务，需要占用$[S_i, T_i]$间的某个时刻，且完成后会有$V_i$的收益。求最大收益。 澄清：一个时刻只能做一件任务，做一个任务也只需要一个时刻。$N≤5000$，$1 \leq Si \leq Ti \leq 10^8$，$1 \leq Vi \leq 10^8$。
Input
第一行一个整数$N$,表示可供选择的任务个数. 接下来的第二到第$N+1$行，每行三个数，其中第$i+1$行依次为$S_i$，$T_i$，$V_i$
Output
输出最大收益
这道题一开始想用$KM$算法，然而复杂度不太对……想了半天不会做，去膜了FQW的论文后终于会做了……
FQW的论文写得很详细，我在这里也没有必要多说什么了……大概思路就是使用贪心的思想来优化特殊二分图的匹配，先找出$n$个有用的点，然后再把任务按收益从大到小排个序，依次$check$能否选当前这个任务……感觉方法是在是很神……
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 5010
using namespace std;
typedef long long llg;
struct data{
int l,r,x;
}s[maxn];
int pos[maxn],n,pip[maxn];
llg ans;
bool cmpl(data a,data b){return a.l<b.l;}
bool cmpx(data a,data b){return a.x>b.x;}
bool work(int x,int d){
if(pos[d]>s[x].r) return 0;
if(!pip[d]){pip[d]=x; return 1;}
else
if(s[pip[d]].r<s[x].r) return work(x,d+1);
else if(work(pip[d],d+1)){pip[d]=x;return 1;}
else return 0;
}
int main(){
File("a");
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d %d %d",&s[i].l,&s[i].r,&s[i].x);
sort(s+1,s+n+1,cmpl);
for(int i=1;i<=n;i++) pos[i]=max(pos[i-1]+1,s[i].l);
for(int i=1,j=1;i<=n;i++){
while(pos[j]<s[i].l) j++;
s[i].l=j;
}
sort(s+1,s+n+1,cmpx);
for(int i=1;i<=n;i++) if(work(i,s[i].l)) ans+=s[i].x;
printf("%lld",ans);
return 0;
}
BZOJ 2034 【2009国家集训队】 最大收益
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。