Posted on 2011-10-05 09:42
Mato_No1 閱讀(1629)
評論(0) 編輯 收藏 引用 所屬分類:
BZOJ
【1】
BZOJ1571DP題，寫起來比較繁瑣……
首先轉移方程是不難想的囧……F[i][j]，表示i時間后能力為j，
然后要設一些輔助數組，G[i]表示F[i][1..MAXJ]的最大值，H2[i]表示能力不超過i的一次滑雪的最小時間（這個還要用一個H1[i]表示能力剛好為i的來輔助求出）……
剩下的也就傻掉了，
當然，WJMZBMR神犇用記憶化搜索……省去了一些計算量……有效縮短時間……Orz啊……
（其實，如果大多數狀態都是無效狀態或者根本導不出最優解的狀態，可以用記憶化的……）
代碼【2】
BZOJ1572任務調度問題（貪心模型）的加強版，用堆優化囧……
先把所有的任務按照結束時間遞減排序，然后掃描，對于當前任務A[i]，結束時間為T[i]，上一個任務A[i-1]的結束時間為T[i-1]，設D=T[i-1]-T[i]，則在堆中取出收益最大的D個任務（顯然該堆是以收益為關鍵字的大頂堆），用它們填上[T[i]+1, T[i-1]]這個時間段（原因很簡單，A[i]及以后的任務在T[i]時刻以前就結束了，不能插入到此段內，因此此段內只能插入A[i-1]及其以前的，也就是在堆中的任務），若堆中的任務數<D，則全部取出，進行完這一步后，再將A[i]插入到堆中即可。
總時間復雜度：O(NlogN)；
代碼【3】
BZOJ1574很容易想到最小點割（怎么看怎么像囧），但它和最小點割又不一樣，因為本題是求T部分點數最少的點割……
正解仍然是貪心。對于每個報告點，由于它沒壞且到1沒有只經過未壞點的路徑，所以與它相鄰的所有的點要么是壞點，要么到1也沒有路徑，因此可以認為它們都是壞點（在最優方案中一定是這樣），這樣標記出所有的壞點以后，從1開始做一次遍歷（只經過未壞點的），最終結果就是遍歷到的點數；
代碼【4】
BZOJ1575裸的DP題啊啊……關鍵是本沙茶WA了N次還用暴搜代碼來對拍啊啊……被折磨死了啊啊……
簡單講一下易疵點：
<1>不可把兩邊都加上一個0來簡化，因為前兩條（處理兩邊的）規則和加上0之后的并不等價；
<2>注意邊界點（i=0或j=1時）的情況；
<3>注意最終結果，要在F[0..N-1]中找最小的合法的j而不是只在F[N-1]中找；
代碼