整體感覺偏難 然後...都是DP?


程式實作 高級 回到考後討論
50_y3gp4 2026-11-01 20:52

1.給定一棵樹,每個節點有正權重,選擇一些節點,使每條邊都至少有一個節點被選到,試問選擇的節點的最小權重和。

2.一個 \(m\times n\) 的網格( \(m,n<10^3\) ),每條邊有 \(-100\sim 100\) 的權重,可以任選一個起點,向右、左或下行走到另一節點形成一路徑(不重疊),試問路徑上權重和的最大值。

3.一個至多40位,且位數中不包含0的正整數字串,將其以數個 \(+\) 分隔(可以為0個)並計算所有能產生的值,另外給定正整數 \(m<3\times 10^3\) ,試問能產生的值中不超過m的最大值是多少、有多少種方法能產生該值。

8 則回覆

Flashingtw 2026-11-01 22:39

我覺得第三題比較難, 其餘都算經典題 第二題要好好實作(x

aacpschool 老師 2026-11-01 22:46
這則含解法,想自己再想想就先不要點開

搭版分享一下我這次參加高級的心得 XD

此題一看完就聯想到考古題 病毒演化,很明顯是個樹 DP 題,而且子問題一樣都是:對於每個子樹,樹根做什麼選擇。病毒演化樹根有 A、U、C、G 四種選擇,而這題就只有選和不選兩種,所以這題實作起來更簡單,當樹根不選時,樹根的所有子節點都一定要選,而樹根選時,所有子節點可選可不選,挑比較好的那個即可。

此題一看完就聯想...不對,不是聯想,根本就一模一樣吧!!!不就是考古題 勇者修煉 從權重在點上改成在邊上嗎?狀態設計完全一樣就可以解決啦!只是轉移式稍微改一下而已。

這樣看來,此次 APCS 高級考古題熟練的人就能穩穩拿下 2 道題然後取得實作 5 級了(?)

此題乍看之下字串長度 \(\le 40\) 很容易聯想到折半枚舉,但我覺得此題用折半枚舉的實作量應該超出高級範圍了,再仔細看題就發現 \(M\) 的值最大其實才 \(3 \times 10^4\),那不就輕鬆 dp 嗎!?畢竟如果我們此題要遞迴(backtracking)寫暴力搜索,直覺的寫法應該會是:dfs(上一個加號放的位置, 目前的數字和),而遞迴裡就是枚舉下一個加號放在哪,而且距離上一個加號位置不會超過 \(5\),而往往遞迴寫暴力搜索的實作方式會是動態規劃狀態設計的提示!這意思是遞迴的參數可能可以直接拿來當 dp 的參數用,於是此題的 dp 狀態就設計出來了:dp[i][v] = 加號要放在第 i 個字元之後,只考慮前 i 個字元穿插加號後,式子運算結果是 v 的有幾個,轉移至多只要枚舉 5 位數即可。

登入後就能回覆。