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 閱讀(316)
評論(0) 編輯 收藏 引用 所屬分類:
topcoder