前言:069三道純思維 + 一道不可做圖論．就沒寫博客了．．
C.水
D.背包dp灿意，思維
題意:給你一個(gè)序列．它的子集Ｓ被稱為好子集腔呜，當(dāng)它的數(shù)字和 >= k. 然后對(duì)于任意一個(gè)序列里的數(shù)x.若ｘ所在的所有集合都可以去除它后依舊是好集合，則稱x為沒必要的．問(wèn)你有多少個(gè)數(shù)是沒必要的．
子問(wèn)題: n <= 300
總: n <= 5000.
子問(wèn)題: 將一個(gè)數(shù)x拿出來(lái)江掩，對(duì)其他數(shù)做ｄｐ．當(dāng)區(qū)間[k - x , k] 中有值能被組成時(shí)学辱，它就是有意義的．跑n遍背包．復(fù)雜度:
總問(wèn)題:
注意到，若某個(gè)比Ｘ小的數(shù)有意義环形，那么Ｘ就是有意義的．
所以根據(jù)上述定義容易推出：無(wú)意義的數(shù)一定是從小到大序列中的一段前綴.
方法一:沿用子問(wèn)題方法策泣，用二分優(yōu)化．復(fù)雜度:,不知道過(guò)不過(guò)的去
方法二:進(jìn)一步思考:若一個(gè)數(shù)Ｘ需要借助比他小的數(shù)來(lái)達(dá)成有意義的．那么那個(gè)比他小的數(shù)就是有意義的．那么Ｘ自然也就是有意義的．所以我們直接從大往小dp.得到最小的有意義的數(shù)的位置pos.答案就是pos - 1.
E.神仙dp
題目大意：有ｎ層，每一層有一個(gè)區(qū)間[Li,Ri].你可以平行的移動(dòng)一段區(qū)間整數(shù)距離抬吟，花費(fèi)就是移動(dòng)的距離.
問(wèn)你最小的花費(fèi)使他們連通．
子問(wèn)題: n , l , r <= 400.
總問(wèn)題: n <= 1e5. l , r <= 1e9
子問(wèn)題解法:容易想到代表保證前ｉ層連通萨咕，最后一層的左端點(diǎn)位于j位置的最小花費(fèi)．
轉(zhuǎn)移即可.
總問(wèn)題解法:斜率優(yōu)化.待補(bǔ).
