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有关联.