题解

51 条题解

  • 7
    @ 2017-04-22 20:12:34
    #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

  • 3
    @ 2013-12-24 16:20:17

    我在这上面写了很多 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

  • 1
    @ 2013-08-07 13:17:42

    //栈+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.

  • 0
    @ 2019-09-05 20:59:28

    纯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;
    }
    
  • 0
    @ 2017-10-26 09:54:35

    先排序 在利用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';
    }
    
  • 0
    @ 2015-08-09 16:12:56

    单调队列+优先队列+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;
    }

  • 0
    @ 2013-09-15 09:29:01

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

  • 0
    @ 2013-03-28 21:09:50

    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.

  • 0
    @ 2010-04-13 23:05:25

    这个什么数据啊。。。

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

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

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

  • 0
    @ 2010-03-12 19:26:08

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

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

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

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

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

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

  • 0
    @ 2009-11-07 17:29:25

    完美的最短路构图...

    可惜还是没想到...

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

  • 0
    @ 2009-11-07 10:37:12

    。用Spfa做的。

    类似与差分约束。

    怎么做就不多说了。

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

    为大家提供个数据。

    3 0 5

    0 7 3

    -2 8 2

    1 1 1

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

    另外注意下内存吧^.^

  • 0
    @ 2009-10-07 15:38:01

    线段树比较直观。

    树状数组,求这个最值。

    恩。

    这道题比较特殊吧。

    把模型倒过来居然可以。

    学到新东西了。

    这个很巧妙啊

  • 0
    @ 2009-10-03 09:36:09

    编译通过...

    ├ 测试数据 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 是 坐标范围

  • 0
    @ 2009-09-14 13:33:51

    编译通过...

  • 0
    @ 2009-08-25 00:15:27

    膜拜oimaster的点击此处

  • 0
    @ 2009-08-11 11:50:45

    编译通过...

    ├ 测试数据 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

  • 0
    @ 2009-07-18 14:50:30

    无耻的二分 让我交了 12编

    二种优化方法: 线段树,,单调队列(比线段树还要无耻)

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

    这道题目要仔细

  • 0
    @ 2009-07-05 18:38:06

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

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

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

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

    对于每个人的 a b cost

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

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

信息

ID
1404
难度
8
分类
动态规划 | 数据结构 | 树状数组数据结构 | 线段树数据结构 | 单调队列其他 | 二分查找图结构 | 最短路 点击显示
标签
(无)
递交数
2877
已通过
415
通过率
14%
上传者