• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            pku3171 Cleaning Shifts 區間最小權覆蓋,DP+單調隊列

            題意是這樣:有N個牛,可以為FJ工作一段時間[si,ti],FJ要支付給他pi工資。FJ需要整天都有牛為他工作,問他至少需要支付多少錢。
            首先,可以對區間按照右端點為第一關鍵字排序,狀態dp[pos]表示聘用第pos個牛時并且之前的區間都已經覆蓋需要支付的錢,一個樸素的DP轉移可以表示為
            dp[pos]=min{dp[i]} ei>=si。當然,我們立刻會發現一點,如果決策dp[j]>dp[i],而j<i,即ej<ei,那么j這個決策是多余的。因此,我們可以維護一個單調隊列,通過二分查找來找到滿足ei>=si的dp[i]最小值,整個算法復雜度nlogn。
            具體分析見周大牛論文/Files/yzhw/range.rar

             1import java.io.*;
             2import java.util.*;
             3class node implements Comparable<node>
             4{
             5    int s,e,val;
             6    public int compareTo(node pos)
             7    {
             8        return e-pos.e;
             9    }

            10}

            11public class Main {
            12
            13    /**
            14     * @param args
            15     */

            16    static node arr[];
            17    static int dp[];
            18    static int stack[][],top=-1;
            19    static int search(int pos)
            20    {
            21        int s=0,e=top,mid=0;
            22        while(s<=e)
            23        {
            24            mid=(s+e)/2;
            25            if(stack[mid][1]>=pos)
            26                e=mid-1;
            27            else
            28                s=mid+1;
            29        }

            30        return s;
            31    }

            32    public static void main(String[] args) throws IOException{
            33        Scanner in=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
            34        int n=in.nextInt(),m=in.nextInt(),e=in.nextInt();
            35        arr=new node[n];
            36        dp=new int[n];
            37        stack=new int[n][2];
            38        for(int i=0;i<arr.length;i++)
            39        {
            40            arr[i]=new node();
            41            arr[i].s=in.nextInt();
            42            arr[i].e=in.nextInt();
            43            if(arr[i].e<arr[i].s)
            44            {
            45                int t=arr[i].e;
            46                arr[i].e=arr[i].s;
            47                arr[i].s=t;
            48            }

            49            arr[i].val=in.nextInt();
            50        }

            51        Arrays.sort(arr);
            52        int i,ans=Integer.MAX_VALUE;
            53        for(i=0;arr[i].s>m&&i<n;i++);
            54        if(i>=n||arr[n-1].e<e) System.out.println(-1);
            55        else
            56        {
            57            dp[i]=arr[i].val;
            58            if(arr[i].e>=e) ans=Math.min(ans, dp[i]);
            59            stack[++top][0]=dp[i];
            60            stack[top][1]=arr[i].e;
            61            for(++i;i<n;i++)
            62            {
            63                int pos=search(arr[i].s-1);
            64                if(pos>top)
            65                    if(arr[i].s<=m)
            66                        dp[i]=arr[i].val;
            67                    else
            68                        continue;
            69                else
            70                {
            71                    dp[i]=stack[pos][0]+arr[i].val;
            72                    if(arr[i].s<=m)
            73                        dp[i]=Math.min(dp[i], arr[i].val);
            74                }

            75                while(top>=0&&stack[top][0]>=dp[i]) top--;
            76                stack[++top][0]=dp[i];
            77                stack[top][1]=arr[i].e;
            78                if(arr[i].e>=e) ans=Math.min(ans, dp[i]);
            79            }

            80            if(ans==Integer.MAX_VALUE)
            81                System.out.println(-1);
            82            else
            83                System.out.println(ans);
            84        }

            85        
            86        
            87    }

            88
            89}

            90
            91


             

             

            posted on 2010-11-02 02:21 yzhw 閱讀(292) 評論(0)  編輯 收藏 引用 所屬分類: DP

            <2010年11月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            亚洲AV无码久久精品蜜桃| 91久久九九无码成人网站| 国产精品久久久香蕉| 99久久99久久精品国产片果冻| 无码人妻少妇久久中文字幕蜜桃 | 久久国产精品成人影院| 国产巨作麻豆欧美亚洲综合久久| 日韩美女18网站久久精品| 久久Av无码精品人妻系列| 精品久久久久久久久久久久久久久| 中文字幕无码av激情不卡久久| 久久亚洲私人国产精品| 久久精品国产黑森林| 久久人人爽人人爽人人片AV不 | 国产精品无码久久综合| 青青久久精品国产免费看| 国产精品禁18久久久夂久| 久久夜色撩人精品国产| 国产精品一区二区久久| 久久久久久国产a免费观看黄色大片 | 亚洲国产精久久久久久久| 久久精品国产99久久久古代| 国产精品无码久久久久| 久久精品国产亚洲AV无码麻豆| 久久久久久久久久免免费精品| 国产V亚洲V天堂无码久久久| 久久天天躁狠狠躁夜夜2020一| 中文精品久久久久国产网址| 久久精品无码专区免费东京热 | 国产精品免费久久久久影院| 国产精品久久久亚洲| 午夜人妻久久久久久久久| 日韩精品久久久久久久电影| 久久久久国产精品三级网| 97久久精品人人做人人爽| 亚洲国产成人久久精品影视| WWW婷婷AV久久久影片| 99久久99久久久精品齐齐| 婷婷综合久久中文字幕蜜桃三电影| 一级做a爰片久久毛片免费陪| 亚洲精品无码久久久久AV麻豆|