| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 4721 | Accepted: 1593 |
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
题意就是给你一些小区间，用小区间去覆盖大区间，求最小花费。
数据结构优化动态规划，这是一个区间最值问题。
将小区间按照右端点排序，然后遍历小区间，每次都找小区间左边到小区间右边的最小值，然后最小值更新，只单点更新右端点就可以(降维)。
一开始想的区间更新，按照贴纸，直接成段更新，后来发现思路是错的，因为区间更新会覆盖掉其他的值。所以要用单点更新。
线段树每个点表示到当前区间段的最优解，直接初始化为inf，然后M-1更新为0，就可以。
每次都是查找a[i].l-1到a[i].r的最小值(因为是片段，所以从a[i].l-1开始查找)，然后更新a[i].r。直接线段树维护区间的最小值。
动态规划方程式就是dp[i]=min(query(a[i].l-1,a[i].r))+a[i].val;表示覆盖到a[i].r的最小花费。因为小区间不能间断，所以要这样查询更新。
因为直接遍历的，所以dp[i]这个方程式都可以省略，直接查值然后更新值到线段树里就可以了。
因为每次都是从a[i].l-1开始，而且题目数据最小可能为0，所以直接端点都+2，这样，最小的值查找的时候也是从1开始的。
写题的时候，不能乱秀，容易把自己秀死。。。
自己写的时候，特判了一下如果最左端点和最端点不能包含大区间，直接-1输出。结果忘了我是按照右端点排序的，右边是对的，左边的不一定是对的。。。
最后直接查询大区间右端点和小区间最右端点。判断一下值就可以了。
如果ans<inf说明都能覆盖到，如果有inf说明有的地方没被覆盖到。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii; const double PI=acos(-1.0);
const double eps=1e-;
const ll mod=1e9+;
const ll inf=1e18;
const int maxn=1e5+;
const int maxm=+;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 struct node{
int l,r;
ll val; friend bool operator<(node a,node b){
if(a.r==b.r) return a.l<b.l;
return a.r<b.r;
} }a[maxn]; ll tree[maxn<<]; void pushup(int rt)
{
tree[rt]=min(tree[rt<<],tree[rt<<|]);
} void build(int l,int r,int rt)
{
if(l==r){
tree[rt]=inf;
return ;
} int m=(l+r)>>;
build(lson);
build(rson);
pushup(rt);
} void update(int pos,ll c,int l,int r,int rt)
{
if(l==r){
tree[rt]=min(tree[rt],c);
return ;
} int m=(l+r)>>;
if(pos<=m) update(pos,c,lson);
if(pos> m) update(pos,c,rson);
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 ret=inf;
if(L<=m) ret=min(ret,query(L,R,lson));
if(R> m) ret=min(ret,query(L,R,rson));
return ret;
} int main()
{
int n,M,E;
cin>>n>>M>>E;
for(int i=;i<=n;i++){
cin>>a[i].l>>a[i].r>>a[i].val;
a[i].l+=,a[i].r+=;
}
M+=,E+=;
sort(a+,a++n);
build(,maxn,);
update(M-,,,maxn,);
for(int i=;i<=n;i++){
ll cnt=query(a[i].l-,a[i].r,,maxn,);
cnt+=a[i].val;
update(a[i].r,cnt,,maxn,);
}
ll ans=query(E,a[n].r,,maxn,);
if(ans<inf) cout<<ans<<endl;
else cout<<"-1"<<endl;
}
OK了。