Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 3563 | Accepted: 1205 |
Description
Farmer John has N (1 <= N <= 10,000) cows who are willing to do some cleaning. Because dust falls continuously, the cows require that the farm be continuously cleaned during the workday, which runs from second number M to second number E during the day (0 <= M <= E <= 86,399). Note that the total number of seconds during which cleaning is to take place is E-M+1. During any given second M..E, at least one cow must be cleaning.
Each cow has submitted a job application indicating her willingness to work during a certain interval T1..T2 (where M <= T1 <= T2 <= E) for a certain salary of S (where 0 <= S <= 500,000). Note that a cow who indicated the interval 10..20 would work for 11 seconds, not 10. Farmer John must either accept or reject each individual application; he may NOT ask a cow to work only a fraction of the time it indicated and receive a corresponding fraction of the salary.
Find a schedule in which every second of the workday is covered by at least one cow and which minimizes the total salary that goes to the cows.
Input
Lines 2..N+1: Line i+1 describes cow i's schedule with three space-separated integers: T1, T2, and S.
Output
Sample Input
3 0 4
0 2 3
3 4 2
0 0 1
Sample Output
5
Hint
FJ has three cows, and the barn needs to be cleaned from second 0 to second 4. The first cow is willing to work during seconds 0, 1, and 2 for a total salary of 3, etc.
Farmer John can hire the first two cows.
Source
//容易想到dp但是没想到可以用线段树处理区间最小值,dp[i]表示到达时间i
//时的最小花费,将区间按照右值从小到大排序,然后枚举区间右值,
//dp[r]=min(dp[r],min(dp[l-1~r-1])+w),其中后一项用线段树处理区间最小值。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=;
const int maxm=;
int n,m,e,minv[maxm*],f[maxm];
struct Lu{
int l,r,w;
Lu(){}
Lu(int a,int b,int c):l(a),r(b),w(c){}
bool operator < (const Lu &p)const{
return r<p.r;
}
}L[maxn];
void pushup(int rt){
minv[rt]=min(minv[rt<<],minv[rt<<|]);
}
void build(int l,int r,int rt){
minv[rt]=inf;
if(l==r) return;
int mid=(l+r)>>;
build(l,mid,rt<<);
build(mid+,r,rt<<|);
pushup(rt);
}
void update(int id,int v,int l,int r,int rt){
if(l==r){
minv[rt]=v;
return;
}
int mid=(l+r)>>;
if(id<=mid) update(id,v,l,mid,rt<<);
else update(id,v,mid+,r,rt<<|);
pushup(rt);
}
int query(int ql,int qr,int l,int r,int rt){
if(ql<=l&&qr>=r)
return minv[rt];
int mid=(l+r)>>,ans=inf;
if(ql<=mid) ans=min(ans,query(ql,qr,l,mid,rt<<));
if(qr>mid) ans=min(ans,query(ql,qr,mid+,r,rt<<|));
return ans;
}
int main()
{
while(scanf("%d%d%d",&n,&m,&e)==){
e-=m; //将区间左移到从0开始
int cnt=;
for(int i=;i<n;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(y<m||x>e) continue; //去掉不可行的区间
x-=m;y-=m;
if(x<) x=;
if(y>e) y=e;
L[cnt++]=Lu(x,y,z);
}
sort(L,L+cnt);
memset(f,inf,sizeof(f));
build(,e,);
for(int i=;i<n;i++){
int tmp=inf;
if(L[i].l==) tmp=L[i].w;
else tmp=query(L[i].l-,L[i].r-,,e,)+L[i].w;
f[L[i].r]=min(f[L[i].r],tmp);
if(f[L[i].r]<inf)
update(L[i].r,f[L[i].r],,e,);
}
if(f[e]>=inf) f[e]=-;
printf("%d\n",f[e]);
}
return ;
}