陳敍安 -
P2279 [HNOI2003] 消防局的設立 題解加總結
正題之前
又是一道抓耳撓腮想了好久的好題， AC 了之後，感覺自己的思想又得到了洗禮 QwQ ，第一次寫題解，有錯望老師見諒
題目傳送門
思路
因為題目求的是覆蓋樹上所有點的所放置最少的消防站數量，因此此題需使用樹形 DP 解決
狀態申明
因為每個"消防局"能覆蓋與它距離不超過 2 的節點 ，因此
總共設有5個狀態
dp[x][0] 為覆蓋到 \(x\) 的爺爺（包括父親）和 \(x\
後端
陳敍安 -
熱身賽總結 題解
1. 旅行計劃
賽時思路
因為目標是：求出一直向東以城市 \(i\) 為終點最多能夠遊覽多少個城市，我進行逆向思維，轉換題意，將目標改成：以城市 \(i\) 為起點一直向西最多能夠遊覽多少個城市，再看題目的數據範圍：$n \le 10^5 $，因此便直接用 dfs 進行搜索，最後 TLE 了4個點 QwQ 。
改進思路
因為題目中説圖中沒有環，因此我們可以通過 DP 解決此題，所以我們就可以通過記
後端
陳敍安 -
比賽題解 總結
1.[HNOI2003] 操作系統
思路
此題是一道大模擬，主要根據任務優先級來計算最後執行此任務的時間，此時我們可以進行分類討論：
當此任務的到達時間晚於等於上一個未執行完任務的結束時間，上一個任務就一定能運行完，因此直接輸出結束時間
當此任務的到達時間早於上一個未執行完任務的結束時間，上一個任務就只能在 CPU 中運行一段時間，因此只能更新執行時間
因為執行任務要看其優先級，因
c++
