• <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>

            pku1337 A Lazy Worker 很詭異的DP

            題意:
            很多人這題題目讀不懂,我詳細(xì)解釋下:一個(gè)懶工人,他想工作的時(shí)間盡量少。有N個(gè)任務(wù),每個(gè)任務(wù)有開始時(shí)間和deadline,工人完成這個(gè)工作需要ti時(shí)間。如果某個(gè)時(shí)刻有工作可以做(這里是說(shuō),如果從這個(gè)時(shí)刻開始某個(gè)工作,在deadline之前能夠完成),那么這個(gè)工人必須做,但是如果這個(gè)時(shí)刻存在著多余1件工作可以做,工人可以選擇;假設(shè)這個(gè)時(shí)刻沒有工作可以做了,工人就可以偷懶直到有新的任務(wù)到來(lái)。

            解法:
            這題初看覺得很麻煩,但是題目中有句話太給力了! You should note that for each job i, the length of Ii, di - ai, is greater than or equal to ti, but less than 2*ti
            這句話把后效性全部消除了,即不可能出現(xiàn)這種情況,在t1這個(gè)決策點(diǎn)出現(xiàn)了第k個(gè)工作,在t1后的某個(gè)決策點(diǎn)t2又出現(xiàn)了第k個(gè)工作,明白了?
            DP方程:
            dp[t]=min(work[i]+dp[t+work[i]]) work指在第t個(gè)時(shí)間點(diǎn)能夠可以開始做的工作
            如果在第t個(gè)時(shí)刻沒有任務(wù)可做,那么dp[t]=dp[t+1]

            代碼:
             1 //============================================================================
             2 // Name        : pku1337.cpp
             3 // Author      : yzhw
             4 // Version     :
             5 // Copyright   : yzhw
             6 // Description : Hello World in C++, Ansi-style
             7 //============================================================================
             8 
             9 #include <iostream>
            10 #include <algorithm>
            11 #include <vector>
            12 #include <cstring>
            13 using namespace std;
            14 vector<int> work[251];
            15 int data[101][3],n,minnum,maxnum,dp[300];
            16 int getdp(int t)
            17 {
            18     if(t>maxnum) return 0;
            19     else return dp[t];
            20 }
            21 int main() {
            22     int test;
            23     cin>>test;
            24     while(test--)
            25     {
            26         cin>>n;
            27         minnum=300;
            28         maxnum=-1;
            29         for(int i=0;i<=250;i++)
            30             work[i].clear();
            31         for(int i=0;i<n;i++)
            32         {
            33             cin>>data[i][0]>>data[i][1]>>data[i][2];
            34             for(int j=data[i][1];j+data[i][0]<=data[i][2];j++)
            35                 work[j].push_back(i);
            36             minnum=min(minnum,data[i][1]);
            37             maxnum=max(maxnum,data[i][2]-data[i][0]);
            38         }
            39         memset(dp,0,sizeof(dp));
            40         for(int t=maxnum;t>=minnum;t--)
            41           if(work[t].empty())
            42               dp[t]=dp[t+1];
            43           else
            44           {
            45               dp[t]=data[work[t][0]][0]+getdp(data[work[t][0]][0]+t);
            46               for(int i=1;i<work[t].size();i++)
            47                 dp[t]=min(dp[t],data[work[t][i]][0]+getdp(data[work[t][i]][0]+t));
            48           }
            49         cout<<dp[minnum]<<endl;
            50     }
            51     return 0;
            52 }
            53 

            posted on 2011-01-23 02:44 yzhw 閱讀(282) 評(píng)論(0)  編輯 收藏 引用 所屬分類: DP

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

            導(dǎo)航

            統(tǒng)計(jì)

            公告

            統(tǒng)計(jì)系統(tǒng)

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評(píng)論

            閱讀排行榜

            亚洲精品高清国产一线久久| 亚洲国产精品久久久久网站 | 精品久久久久久久国产潘金莲| 天天久久狠狠色综合| 久久99国产精一区二区三区| 精品久久久久久成人AV| 狠狠色丁香久久婷婷综| 亚洲国产精品久久久久网站 | 99久久99这里只有免费的精品| 久久99热只有频精品8| 国产精品久久自在自线观看| 超级碰久久免费公开视频| 久久国产成人午夜aⅴ影院| 四虎影视久久久免费观看| 日韩va亚洲va欧美va久久| 久久精品国产乱子伦| .精品久久久麻豆国产精品 | 久久综合五月丁香久久激情| 久久久久久久综合综合狠狠| 国产精品久久久久久久人人看| 免费精品久久天干天干| 国产精品美女久久久| 伊人久久一区二区三区无码| 久久九九精品99国产精品| 99久久精品国产一区二区三区| 久久一区二区三区99| 国产Av激情久久无码天堂| 久久精品国产亚洲Aⅴ蜜臀色欲| 伊人久久综合无码成人网| 久久精品国产福利国产秒| 中文字幕无码久久久| 国产一级持黄大片99久久| 人妻精品久久久久中文字幕| 久久99国产精品尤物| 伊人久久大香线蕉精品不卡| 国产韩国精品一区二区三区久久| 亚洲欧美日韩久久精品| 99久久人妻无码精品系列 | 国产精品丝袜久久久久久不卡| 伊人久久综合成人网| 久久久国产亚洲精品|