| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 4422 | Accepted: 1482 |
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
题意：
一个[L, R]的区间，有n头牛，每头牛可以清理一个固定区间，需要花费一定的价格。现在要清理[L,R]这个区间，需要花费最少的价格是多少。
思路：
用f[x]表示清理区间[L, x]需要花费的最小价格。
对于一头牛，他可以清理的区间是[a,b]，那么因为中间不能间断，所以f[b] = min(f[x]) + c其中x是属于[a-1,b]区间的。
每次状态转移都要取一个区间最小值，并且更新一个点的值，所以用上线段树来维护。
首先将所有的牛按照结束的区间进行排序，然后DP。
因为时间是从0开始，所以我给所有的时间都加了2，这样a-1就还是从1开始。
要注意的是update（）时，并不是直接将值改为val，而是取较小值，这里WA了一会。
#include <iostream>
#include <set>
#include <cmath>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
#define inf 0x7f7f7f7f const int maxn = 1e5 + ;
const int maxtime = ;
struct node{
int st, ed, cost;
}cow[maxn];
bool cmp(node a, node b)
{
return a.ed < b.ed;
}
LL tree[maxn << ];//区间中f[]最小值
int n, L, R; void pushup(int rt)
{
tree[rt] = min(tree[rt << ], tree[rt << |]);
} void build(int rt, int l, int r)
{
if(l == r){
tree[maxn] = inf;
return;
}
int mid = (l + r) / ;
build(rt<<, l, mid);
build(rt<<|, mid + , r);
pushup(rt);
} void update(int x, LL val, int l, int r, int rt)
{
if(l == r){
tree[rt] = min(tree[rt], val);
return;
}
int m = (l + r) / ;
if(x <= m){
update(x, val, l, m, rt<<);
}
else{
update(x, val, m + , r, rt<<|);
}
pushup(rt);
} LL query(int L, int R, int l, int r, int rt)
{
if(L <= l && R >= r){
return tree[rt];
}
int m = (l + r) / ;
LL ans = inf;
if(L <= m){
ans = min(ans, query(L, R, l, m, rt<< ));
}
if(R > m){
ans = min(ans, query(L, R, m + , r, rt<<|));
}
pushup(rt);
return ans;
} int main()
{
while(scanf("%d%d%d", &n, &L, &R) != EOF){
L+=;R+=;
memset(tree, 0x7f, sizeof(tree));
for(int i = ; i <= n; i++){
scanf("%d%d%d", &cow[i].st, &cow[i].ed, &cow[i].cost);
cow[i].st+=;cow[i].ed+=;
}
sort(cow + , cow + + n, cmp); build(, , R); update(L - , , , R, );
//cout<<"yes"<<endl;
int far = L;
bool flag = true;
for(int i = ; i <= n; i++){
if(cow[i].st > far + ){
flag = false;
// break;
}
int a = max(L - , cow[i].st - );
int b = min(R, cow[i].ed);
//cout<<a<<" "<<b<<endl;
LL f = query(a, b, , R, );
f += cow[i].cost;
//cout<<f<<endl;
update(b, f, , R, );
far = max(far, cow[i].ed);
//cout<<far<<endl;
}
//cout<<"yes"<<endl; LL ans = query(R, R, , R, );
if(ans >= inf){
printf("-1\n");
}
else{
printf("%lld\n", ans); //else{
// printf("-1\n");
} } }