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

500p DrawingLines
(兩排點,每排n個.上排的和下排的連線.事先已經有些線連好了.求考慮所有的連線方案時,連線交點個數的期望)
三類計數:事先已經連好的線間的交點數.新增連線和原有連線的交點數期望.新增連線之間交點期望.

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

ps.1000p與steiner tree有關聯.