#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)


const int maxn=10000+10,maxm=90000+10;
const int inf=0x3f3f3f3f;

int n,s,e;
struct data {
    int l,r,v;
} b[maxn];
vector<int> a[maxm];
int d[maxm][30];
int f[maxm];
int mx;
int ans=inf;
int query(int l,int r) {
    int k=0;
    while ((1<<(k+1)<=r-l+1)) k++;
    int len=(1<<k);
    return min(d[r][k],d[l+len-1][k]);
}
int main() {
    scanf("%d%d%d",&n,&s,&e);
    FOR(i,n) {
        scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].v);
        a[b[i].r].push_back(i);
        mx=max(mx,b[i].r);
    }
    memset(f,0x3f,sizeof(f));
    memset(d,0x3f,sizeof(d));
    
    for (int i=s;i<=mx;i++) {
        for (int j=0;j<a[i].size();j++) {
        
            int id=a[i][j];
            if (b[id].l<=s) f[i]=min(f[i],b[id].v);
            else {
                int tmp=query(b[id].l-1,b[id].r-1);
                if (tmp==inf) continue;
                f[i]=min(f[i],tmp+b[id].v);
            }
        }
        d[i][0]=f[i];
        for (int k=1;i-(1<<k)+1>=s;k++) {
            d[i][k]=min(d[i][k-1],d[i-(1<<(k-1))][k-1]);
        }
    }
    for (int i=e;i<=mx;i++) {
        ans=min(ans,f[i]);
    }
    if (ans==inf) {
        printf("-1");
    } else printf("%d",ans);
    return 0;
}

思路：
刚开始用枚举第i个区间作为结尾的方式来DP。
但是发现因为区间是可重的所以没有好的转移方式就放弃了这个idea。
然后想了一些别的，直到注意到区间范围不算太大所以开始往枚举覆盖的目标区间[s,i]这一方向上想。
f[i]为选取区间覆盖[s,i]的最小花费。
转移：f[i]=min{f[i-len(j)]+cost(j)} 对于所有以i结尾的区间j
然后发现这个转移是错的，因为最后一个区间不一定恰好覆盖i。
然后把定义改成了最后一个区间右端点恰好覆盖i.
只要转移到最后一个区间覆盖范围内的点就行了。
列出转移方程：
f[i]=min{f[k]+cost(k) j_l-1<=k<=j_r-1,j是以i结尾的区间}
这样就可以用RMQ优化。
记m为最大区间右端点
复杂度为O(m+nlogm)

BUG/教训：
1.原本以为本题没有涉及乘法不会溢出，但是涉及到inf，加上c的时候可能会变负数（c比较大，可以做一下实验），所以要判断。
2.写代码的时候没有保存然后黑屏了要重写，血泪教训QAQ

总结：
在思考方向上多做变换利于解决问题
调试的时候该自信的地方要自信，这样才能快速找出BUG

我在这上面写了很多 http://tieba.baidu.com/p/2772105734

（不过为了防止帖子过久找不到了 还是在这里也写一个）

前段时间做费用流时做过一道类似的题 所以先想到了最短路做法
方法1：按点之间的关系建边 最多n^2条边
然后还可利用有向无环图的性质以O（n+e）的时间求出
但是空间上n^2的边存不下 所以理论上只有70分
方法2：根据坐标范围较小 可以按坐标关系建边
最多n+（e-s）条边 可以存下
至于求最短路 不知为何我的spfaTLE了（只有40）
然后就换成了手打dijkstra+堆 然后153ms

（中间WA过多次 太长时间没手打堆了）

方法3：考虑到N*2<(e-s)(尽管还是一个数量级上的，
但是至少常数会小点）可DP加离散化1000ms
（切记离散做数组要开N*2）
方法4：这个DP是有单调性的 所以可在方法3的基础上

+break优化达到100ms

方法5:：其实之前想到又单调性可break时 就应该往二分单调栈
上想的 不过还是写少了所以不敢随便用吧——写二分改了好几次
最后60ms

顺便说一下，数据随机的情况下 单调性DP nlogn 相对于
n^2+break 不会有明显优越（因为常常每层循环内几次就

break了相当于n*一个不大的常数）

方法6：原来单调队列的方法是按区间左端点排的
而且还要用堆来维护 （一开始还以为是排序之后
直接O（n）解决 于是一直不理解） 最后90ms解决

用堆维护单调性常数肯定会比二分查找大些
但数据随机的话 队列的长度会很小
（一般n=10^4时也就不到100的队列长度吧）

但是此题数据好像不那么随机 于是比单调栈还慢

方法7：每次选取最小值也可以用RMQ来做
然后RMQ的那几种方法中 BIT的常数应该小些

于是选择了BIT 即使离散了还是要75ms

//栈+DP 维护一个f与b都单调递增的栈，取最小值时用二分查找
var
n,s,e,i,min,k,mint,j:longint;
a,b,c,f,st:array[0..10001] of longint;
procedure qs(low,high:longint);
var i,j,mid,t:longint;
begin
i:=low; j:=high; mid:=b[(i+j) div 2];
repeat
while b[i]<mid do inc(i);
while b[j]>mid do dec(j);
if i<=j then
begin
t:=a[i]; a[i]:=a[j]; a[j]:=t;
t:=b[i]; b[i]:=b[j]; b[j]:=t;
t:=c[i]; c[i]:=c[j]; c[j]:=t;
inc(i); dec(j);
end;
until i>j;
if i<high then qs(i,high);
if j>low then qs(low,j);
end;

procedure push(i:longint);
begin
while (f[st[k]]>=f[i]) and (k>0) do dec(k);
inc(k); st[k]:=i;
end;

function find(t:longint):longint;
var l,r,mid:longint;
begin
l:=1; r:=k; if b[st[k]]+1<t then exit(0);
while l<r do
begin
mid:=(l+r) shr 1;
if b[st[mid]]+1>=t then r:=mid
else l:=mid+1;
end;
exit(st[l]);

end;

begin
readln(n,s,e); k:=0;
for i:=1 to n do
readln(a[i],b[i],c[i]);
for i:=0 to n do f[i]:=maxlongint;
qs(1,n);
for i:=1 to n do
begin
if (s>=a[i]) and (s<=b[i]) then begin f[i]:=c[i]; push(i); continue end;
if find(a[i])=0 then continue;
f[i]:=f[find(a[i])]+c[i]; push(i);

end;
min:=maxlongint;
for i:=1 to n do
if (a[i]<=e) and (b[i]>=e) and (f[i]<min) then
min:=f[i];
if min=maxlongint then writeln(-1)
else writeln(min);
end.

纯DP
先对区间做排序，再遍历每个区间做DP，直接取覆盖至该点的最小Cost。

#include <bits/stdc++.h>

using namespace std;

typedef struct
{
    int a,b,e;
}edge;

int n,s,e,l=0;
edge ee[10000];
long long dp[90000];

bool comp(edge a,edge b)
{
    if(a.a==b.a)
    {
        return a.b<b.b;
    }
    else
    {
        return a.a<b.a;
    }
}

int main()
{
    cin>>n>>s>>e;
    int i,j,k,x,y;
    for(i=0;i<n;i++)
    {
        cin>>x>>y>>k;
        if(y>=s||x<=e)
        {
            ee[l].a=x;
            ee[l].b=y;
            ee[l].e=k;
            l++;
        }
    }
    sort(ee,ee+l,comp);
    memset(dp,62,sizeof(dp));
    for(i=0;i<l;i++)
    {
        if(ee[i].a<=s)
        {
            y=ee[i].e;
        }
        else
        {
            y=dp[ee[i].a-1]+ee[i].e;
        }
        for(j=ee[i].a;j<=ee[i].b;j++)
        {
            dp[j]=min(dp[j],(long long)y);
        }
    }
    if(dp[e]>1e9)
    {
        cout<<-1<<endl;
    }
    else
    {
        cout<<dp[e]<<endl;
    }
    return 0;
}

先排序 在利用dp的思想用线段树优化 （先把所有区间向右移1单位会较好处理）

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define lc(x) (((x) << 1))
#define rc(x) (((x) << 1) | 1)
using namespace std;
const int maxn  = 10000 + 5;
const int maxc = 90000 + 5;
int N, S, E;
struct T{
    int s, e, v;
    bool operator < (const T &rhs){
        return rhs.s > s || (rhs.s == s && rhs.e > e);
    }
}t[maxn];
struct Segment_Tree{
    int C[maxc * 4];  
    void build(int L, int R, int x = 1){
        if(L == R){
            C[x] = INF;
            return;
        }
        int M = (L + R) / 2;
        build(L, M, lc(x));
        build(M + 1, R, rc(x));
        C[x] = max(C[lc(x)], C[rc(x)]);
    }
    int getMin(int L, int R, int l, int r, int x = 1){
        if(l <= L && r >= R) return C[x];
        int M = (L + R) / 2, v1 = INF, v2 = INF;
        if(l <= M) v1 = getMin(L, M, l, r, lc(x));
        if(r > M) v2 = getMin(M + 1, R, l, r, rc(x));
        return min(v1, v2);     
    }
    void modify(int L, int R, int q, int v, int x = 1){
        if(L == R){ C[x] = min(C[x], v); return; }
        int M = (L + R) / 2;    
        if(q <= M)modify(L, M, q, v, lc(x));
        else modify(M + 1, R, q, v, rc(x));
        C[x] = min(C[lc(x)], C[rc(x)]);
    }
}ST;
int main(){
    cin >> N >> S >> E; S++, E++;
    int mx = 0;
    for(int i = 0; i < N; i++){
        cin >> t[i].s >> t[i].e >> t[i].v;
        t[i].s++, t[i].e++;
        mx = max(t[i].e, mx); 
    }
    sort(t, t + N);
    ST.build(0, 90000); ST.modify(0, 90000, S - 1, 0);
    for(int i = 0; i < N; i++){
        int s = t[i].s, e = t[i].e, v = t[i].v;
        if(e < S || s > E)continue;
        int sum = ST.getMin(0, 90000, s - 1, e) + v; 
        ST.modify(0, 90000, e, sum);  
    }
    int k = ST.getMin(0, 90000, E, mx); 
    if(k == INF)cout << -1 << '\n';
    else cout << k << '\n';
}

单调队列+优先队列+DP轻松水过~~
#include<iostream>
#include<cstdio>
#include<deque>
#include<queue>
#include<cstring>
#include<algorithm>
#define inf 0x7fffffff/2
#define maxn 10010
using namespace std;
int n,s,e,ans,f[maxn];
struct data{
int r,val;
bool operator<(const data &a)const{
return val>a.val;
}
};
deque<data>Q;
struct man{
int s,e,c;
bool operator<(const man&a)const{
return s<a.s;
}
}da[maxn];
void dp(){
priority_queue<data>Q;
int a;
for(a=1;da[a].s<=s;a++){
if(da[a].e>=s)Q.push((data){da[a].e,da[a].c});
if(da[a].e>=e)ans=min(ans,da[a].c);
}

for(int i=a;i<=n;i++){
if(da[i].s>e)break;
while(!Q.empty()&&Q.top().r+1<da[i].s){
Q.pop();
}
if(Q.empty())return;
int val=Q.top().val+da[i].c;
if(da[i].e<e){
if(da[i].e>Q.top().r)Q.push((data){da[i].e,val});
}else{
ans=min(ans,val);

}
}
}
int main(){
freopen("p1404.in","r",stdin);
freopen("wode.out","w",stdout);
scanf("%d%d%d",&n,&s,&e);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&da[i].s,&da[i].e,&da[i].c);
}
sort(da+1,da+n+1);
for(int i=1;i<=n;i++){
}
int last=s-1;
da[n+1].s=inf;
for(int i=1;i<=n+1;i++){
if(da[i].s>last+1&&s<=last+1&&last<e){
puts("-1");
return 0;
}
last=max(last,da[i].e);
}

ans=inf;
dp();

printf("%d\n",ans);
return 0;
}

。。。一个continue写成break杯具啊

program voj1404;
var
a:array[1..88001] of longint;
s,e,c:array[1..10000] of longint;
i,j,k,p,n,base,time,f,pos:longint;

procedure sort(l,r:longint);
var i,j,mid,temp:longint;
begin
i:=l; j:=r; mid:=e[(l+r)>>1];
repeat
while e[i]<mid do inc(i);
while e[j]>mid do dec(j);
if i<=j then
begin
temp:=s[i]; s[i]:=s[j]; s[j]:=temp;
temp:=e[i]; e[i]:=e[j]; e[j]:=temp;
temp:=c[i]; c[i]:=c[j]; c[j]:=temp;
inc(i); dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

begin
readln(n,base,time); dec(time,base);
for i:=1 to n do
begin
readln(s[i],e[i],c[i]);
dec(s[i],base); dec(e[i],base);
if s[i]<0 then s[i]:=0;
if e[i]>time then e[i]:=time;
end;
sort(1,n); k:=1; fillchar(a,(time+1)<<2,$3F);
for i:=0 to time do
begin
f:=maxlongint>>1;
while (k<=n) and (e[k]=i) do
begin
pos:=time-s[k]+2;
repeat
if a[pos]+c[k]<f then f:=a[pos]+c[k];
dec(pos,pos and -pos);
until pos=0;
inc(k);
end;
pos:=time-i+1;
repeat
if f<a[pos] then a[pos]:=f;
inc(pos,pos and -pos);
until pos>time+1;
end;
if f<$3F3F3F3F then writeln(f) else writeln(-1);
end.

这个什么数据啊。。。

O(NM) 的暴力DP 居然 直接秒杀了 ……

for j:=e[i] downto s[i] do

if (f[j]=infi)or(w

恩……………… 忘了判断无解了，居然白交两次 汗流直下- -！

这题貌似不需要什么高级数据结构的，可以考虑一下SPFA的写法(其实是费用流转的)

构图：对于时刻i，向时刻i-1连容量为1，费用为0的边

对于每个人，从时刻si向时刻ei连容量为1，费用为cost[i]的边

求 开始时刻到结束时刻的非0最小费用最小流

而这题非0最小流一定是1…………，所以简化为去掉容量的图，直接一次SPFA

完美的最短路构图...

可惜还是没想到...

对空间的要求很高...我开了好大的数组才过，AC率...

。用Spfa做的。

类似与差分约束。

怎么做就不多说了。

交了N遍的90分。O.O。万恶的第一个点。

为大家提供个数据。

3 0 5

0 7 3

-2 8 2

1 1 1

..这个数据应该类似于第一个测试点吧。很阴的。。

另外注意下内存吧^.^

线段树比较直观。

树状数组，求这个最值。

恩。

这道题比较特殊吧。

把模型倒过来居然可以。

学到新东西了。

这个很巧妙啊

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

翁*m DP + 一点点优化= 秒杀

m 是 坐标范围

编译通过...

膜拜oimaster的点击此处

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

Orz Jason*

树状数组好强……

program voj1404;

var

a:array[1..88001] of longint;

s,e,c:array[1..10000] of longint;

i,j,k,p,n,base,time,f,pos:longint;

procedure sort(l,r:longint);

var i,j,mid,temp:longint;

begin

i:=l; j:=r; mid:=e[(l+r)>>1];

repeat

while e[i]mid do dec(j);

if ij;

if l

无耻的二分 让我交了 12编

二种优化方法： 线段树，，单调队列（比线段树还要无耻）

http://hi.baidu.com/justhongming 有题解

这道题目要仔细

这题为什么是高级数据结构?

明明是最短路(或者说最大流是1的最小费用最大流)嘛..

有 s,s+1,......e,e+1这些结点

i -> (i-1) 有权为0的有向边

对于每个人的 a b cost

a -> (b+1) 有权为cost的有向边

SPFA求 s->(e+1)最短路即可.

我对此题数据彻底无语了。

第一个点会有人在任务之外有空闲时间，我用线段树处理的时候一直提示216错误。提交了无数次才意识到有这个问题。

我没看懂题解的方法，不会用优先队列之类的东西。我用DP+线段树。以时间为节点，v[t]表示时间守住时间1到t的最小代价。对n个人的结束时间进行排序，从小到大。当考虑第i个人的时候，用v[s[i]-1]+c[i]更新区间v[s[i]]到v[e[i]]。实现更新的方法就是用线段树加一个偷懒变量来实现，时间就变成logn了。