給出一棵節點帶權的樹，節點上可以有陷阱，找一條最多經過C個陷阱的簡單路徑，使得經過的節點權值和最大。另外，一旦訪問到了第C個陷阱，就得立刻停下，路徑不能繼續延伸了。
dp[i][j][k]：以i爲一個端點，另一端在i的子樹內的路徑經過節點權值和的最大值，約束條件有兩個：
- 經過了
j個陷阱 - 端點特性爲
k。k有兩種取值： - 0：表示子樹內的端點必須是陷阱
- 1：表示子樹內的端點可以任取，沒有
k爲0時的限制
之所以引入k是爲了解決題目中要求的一點：當經過第C次陷阱時，必須立刻停下，不能繼續前進。考察從起點到終點沿路節點是否有陷阱，有以下四種情況：
o-...-o：起點、終點皆無陷阱x-...-o：起點無陷阱，終點有陷阱o-...-x：起點無陷阱，終點有陷阱x-...-x：起點、終點皆有陷阱
如果選擇的路徑上恰好有C的陷阱，那麼前兩種情況就是不合法的。因爲一旦經過第C次陷阱就得立刻停下，之後不可能再經過無陷阱的節點。
如果選擇的路徑上有不到C個陷阱，那麼前兩種情況也可以算上。
狀態中的k就是用來區分不合法狀況的，當k爲0時只允許後兩種情況；爲時允許所有四種情況。動態規劃過程計算完畢之後，還要注意最優路徑可能跨立兩棵子樹，我們需要枚舉兩棵子樹的路徑，把它們接合。如果這兩條路徑的陷阱總數不到C，那麼就對端點特性沒有要求(四種情況均可)，對應了代碼中的if (j+k < c) ans = max(ans, dp[u][j][1] + dp[v][k][1]);；如果總數等於C`，那麼路徑的一端必須是陷阱。
Read full article from HDU OJ一些題目 | MaskRay
No comments:
Post a Comment