250p DoorsGame
(一行并列的格子,每個(gè)格子中有某種顏色的障礙物,最多15種顏色.A在最左端,B在最右端...)
15種顏色,可以直接極大極小狀態(tài)DP.
可以直接貪心,計(jì)數(shù)只有A需要拿走的顏色數(shù),只有B需要拿走的,和兩都要拿走的.

500p DrawingLines
(兩排點(diǎn),每排n個(gè).上排的和下排的連線.事先已經(jīng)有些線連好了.求考慮所有的連線方案時(shí),連線交點(diǎn)個(gè)數(shù)的期望)
三類(lèi)計(jì)數(shù):事先已經(jīng)連好的線間的交點(diǎn)數(shù).新增連線和原有連線的交點(diǎn)數(shù)期望.新增連線之間交點(diǎn)期望.

1000p BuildingRoads
若干個(gè)點(diǎn)(<=2500)和若干條邊的無(wú)向圖.每個(gè)點(diǎn)有點(diǎn)權(quán).現(xiàn)在有4對(duì)特殊的點(diǎn).要求選一些路徑出來(lái),使每對(duì)點(diǎn)連通(不同對(duì)間不要求連通),總代價(jià)是經(jīng)過(guò)的所有點(diǎn)權(quán)之和.
雖然只有4對(duì)點(diǎn),但是也不要一口咬定是狀態(tài)DP(250p血的教訓(xùn)),雖然的確是狀態(tài)DP...
最后不同點(diǎn)對(duì)是可以不屬于同一連通分量的,所以只1次DP不容易設(shè)計(jì)狀態(tài).
第1次dp: dp[mask][i], mask表示連通子樹(shù)中包含的特殊點(diǎn), i表示這棵子樹(shù)的代表節(jié)點(diǎn)(or根節(jié)點(diǎn)).
第2次dp: dp2[mask], mask表示已經(jīng)包含的特殊點(diǎn), 不要求是連通的, 但是對(duì)應(yīng)的2個(gè)點(diǎn)要在同一分量.
這個(gè)過(guò)程就像,先把每個(gè)子模塊做好, 再將他們拼接整合.

ps.1000p與steiner tree有關(guān)聯(lián).