【1】BZOJ1571
DP題，寫起來比較繁瑣……
首先轉(zhuǎn)移方程是不難想的囧……F[i][j]，表示i時間后能力為j，
然后要設(shè)一些輔助數(shù)組，G[i]表示F[i][1..MAXJ]的最大值，H2[i]表示能力不超過i的一次滑雪的最小時間（這個還要用一個H1[i]表示能力剛好為i的來輔助求出）……
剩下的也就傻掉了，
當(dāng)然，WJMZBMR神犇用記憶化搜索……省去了一些計算量……有效縮短時間……Orz啊……
（其實(shí)，如果大多數(shù)狀態(tài)都是無效狀態(tài)或者根本導(dǎo)不出最優(yōu)解的狀態(tài)，可以用記憶化的……）
代碼

【2】BZOJ1572
任務(wù)調(diào)度問題（貪心模型）的加強(qiáng)版，用堆優(yōu)化囧……
先把所有的任務(wù)按照結(jié)束時間遞減排序，然后掃描，對于當(dāng)前任務(wù)A[i]，結(jié)束時間為T[i]，上一個任務(wù)A[i-1]的結(jié)束時間為T[i-1]，設(shè)D=T[i-1]-T[i]，則在堆中取出收益最大的D個任務(wù)（顯然該堆是以收益為關(guān)鍵字的大頂堆），用它們填上[T[i]+1, T[i-1]]這個時間段（原因很簡單，A[i]及以后的任務(wù)在T[i]時刻以前就結(jié)束了，不能插入到此段內(nèi)，因此此段內(nèi)只能插入A[i-1]及其以前的，也就是在堆中的任務(wù)），若堆中的任務(wù)數(shù)<D，則全部取出，進(jìn)行完這一步后，再將A[i]插入到堆中即可。
總時間復(fù)雜度：O(NlogN)；
代碼

【3】BZOJ1574
很容易想到最小點(diǎn)割（怎么看怎么像囧），但它和最小點(diǎn)割又不一樣，因?yàn)楸绢}是求T部分點(diǎn)數(shù)最少的點(diǎn)割……
正解仍然是貪心。對于每個報告點(diǎn)，由于它沒壞且到1沒有只經(jīng)過未壞點(diǎn)的路徑，所以與它相鄰的所有的點(diǎn)要么是壞點(diǎn)，要么到1也沒有路徑，因此可以認(rèn)為它們都是壞點(diǎn)（在最優(yōu)方案中一定是這樣），這樣標(biāo)記出所有的壞點(diǎn)以后，從1開始做一次遍歷（只經(jīng)過未壞點(diǎn)的），最終結(jié)果就是遍歷到的點(diǎn)數(shù)；
代碼

【4】BZOJ1575
裸的DP題啊啊……關(guān)鍵是本沙茶WA了N次還用暴搜代碼來對拍啊啊……被折磨死了啊啊……
簡單講一下易疵點(diǎn)：
<1>不可把兩邊都加上一個0來簡化，因?yàn)榍皟蓷l（處理兩邊的）規(guī)則和加上0之后的并不等價；
<2>注意邊界點(diǎn)（i=0或j=1時）的情況；
<3>注意最終結(jié)果，要在F[0..N-1]中找最小的合法的j而不是只在F[N-1]中找；
代碼