250p DoorsGame(一行并列的格子,每個格子中有某種顏色的障礙物,最多15種顏色.A在最左端,B在最右端...)
15種顏色,可以直接極大極小狀態(tài)DP.
可以直接貪心,計數只有A需要拿走的顏色數,只有B需要拿走的,和兩都要拿走的.
500p DrawingLines(兩排點,每排n個.上排的和下排的連線.事先已經有些線連好了.求考慮所有的連線方案時,連線交點個數的期望)
三類計數:事先已經連好的線間的交點數.新增連線和原有連線的交點數期望.新增連線之間交點期望.
1000p BuildingRoads若干個點(<=2500)和若干條邊的無向圖.每個點有點權.現在有4對特殊的點.要求選一些路徑出來,使每對點連通(不同對間不要求連通),總代價是經過的所有點權之和.
雖然只有4對點,但是也不要一口咬定是狀態(tài)DP(250p血的教訓),雖然的確是狀態(tài)DP...
最后不同點對是可以不屬于同一連通分量的,所以只1次DP不容易設計狀態(tài).
第1次dp: dp[mask][i], mask表示連通子樹中包含的特殊點, i表示這棵子樹的代表節(jié)點(or根節(jié)點).
第2次dp: dp2[mask], mask表示已經包含的特殊點, 不要求是連通的, 但是對應的2個點要在同一分量.
這個過程就像,先把每個子模塊做好, 再將他們拼接整合.
ps.1000p與steiner tree有關聯(lián).
posted on 2010-05-28 00:02
wolf5x 閱讀(268)
評論(0) 編輯 收藏 引用 所屬分類:
topcoder