• <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>
            posts - 43,  comments - 9,  trackbacks - 0
            250p TheMoviesLevelOneDivOne
            電影院有n行m列的座位, 有一些已經被預訂了. 求在剩下的座位中, 選出同行且相鄰的兩個座位的方案數.
            可以按行列將已預訂的座位排序, 然后順便掃一遍, 算出相鄰兩個被預訂座位之間的方案數. 最后累加.
            也可以用個set記錄不能使用的方案, 再用沒有預訂座位的情況下的總方案數減去之.

            500p TheMoviesLevelTwoDivOne
            若干部電影, 每部電影有一個加血的時間點. 人看電影, 每看一分鐘掉一點血. 血掉到0就結束. 問怎樣按排順序使看的電影部數最多. 如果總部數相同, 取字典序最小的解輸出.
            只有20部電影, 狀態DP即可.
            為保證字典序, 可以從后往前DP, 這樣每次轉移時新加入的電影都是當前最先看的, 保證它先擇的是最小的, 即能保證字典序最小.

            [DP]

            1000p TheMoviesLevelThreeDivOne
            若干部電影, A和B兩人看每部電影的時間分別是A[i], B[i]. 初始安排, 要依次把第1,2,..,n部電影放入A或B的待看隊列的隊尾. A和B各自開始看自己隊列中的電影, 看完一部后, 如果這是另一個人沒看過的, 就加入它的隊列中. 如果期間某人列隊空了, 那么他就結束, 再也不看新電影了. 問有多少種初始安排方法, 能使A和B都能看完所有電影.
            首先肯定不會出現一種安排使得A和B都卡. 因為A卡肯定發生在A看完他所有的電影之后, 且此時B沒看完自己的, 所以B肯定不會卡.
            這樣就可以用總方案數2^N分別減去A卡的和B卡的方案數. 考慮A卡的情況. 假設A那一整坨東西的時長是sumA, B的第一個東西是tb1, 則A卡的條件是 sumA-tb1<0. 否則B看完tb1后把ta1加在sumA后面, 這時卡的條件是(sumA+ta1)-(tb1+tb2)<0. 依此, 如果在這過程中任意一次卡的條件符合, 那么后續怎么安排都是卡的. 于是用一維狀態記錄目前為止出現過的最小的X-Y, min, 還要一維記錄當前的X-Y, cur, 以轉移用. 轉移時, 如果把當前電影放進A, 那么min和cur都增加A[i], 因為sumA增加了. 如果放進B, 那么用cur和B[i]來計算新的cur和min.
            hint. cur=當前所有電影的A[i]的和-B中電影的B[i]的和, 新的min=除了新放的電影外所有放過的電影的A[i]的和-包括新電影在內的B中電影的B[i]的和.

            ps. 1000的DP都很YD啊...

            [DP]
            posted on 2010-05-29 14:40 wolf5x 閱讀(295) 評論(0)  編輯 收藏 引用 所屬分類: topcoder
            <2010年5月>
            2526272829301
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            "Do not spend all your time on training or studying - this way you will probably become very exhausted and unwilling to compete more. Whatever you do - have fun. Once you find programming is no fun anymore – drop it. Play soccer, find a girlfriend, study something not related to programming, just live a life - programming contests are only programming contests, and nothing more. Don't let them become your life - for your life is much more interesting and colorful." -- Petr

            留言簿(3)

            隨筆分類(59)

            隨筆檔案(43)

            cows

            搜索

            •  

            最新評論

            評論排行榜

            99久久免费国产特黄| 久久综合给久久狠狠97色 | 久久久精品视频免费观看| 一本大道久久a久久精品综合 | 97热久久免费频精品99| 久久99国产精品久久99| 久久婷婷色综合一区二区| 亚洲国产天堂久久久久久| 久久夜色精品国产噜噜亚洲AV| 久久精品国产只有精品2020| 久久e热在这里只有国产中文精品99 | 大香伊人久久精品一区二区| 久久婷婷五月综合97色| 久久国产热这里只有精品| 狠狠色丁香久久婷婷综合| 午夜不卡888久久| 久久婷婷激情综合色综合俺也去| 久久精品三级视频| 久久国产精品-国产精品| 伊人久久大香线蕉av不变影院| 久久久久无码精品| 91精品国产色综合久久| 色综合久久综合中文综合网| 久久午夜无码鲁丝片午夜精品| 狠狠色丁香久久综合五月| 日韩AV无码久久一区二区| 中文字幕久久精品| 精品人妻伦九区久久AAA片69| 国产精品久久久久9999| 久久久国产乱子伦精品作者| 中文字幕久久久久人妻| 久久精品国产男包| 久久综合亚洲鲁鲁五月天| 精品国产91久久久久久久a | 少妇久久久久久久久久| 久久青青草视频| 人妻无码精品久久亚瑟影视| 久久久久亚洲av综合波多野结衣| 亚洲精品视频久久久| 四虎国产精品成人免费久久| 亚洲AⅤ优女AV综合久久久|