×
解除綁定,重新設定系統帳號的密碼
您的系統帳號 ID:
您的系統帳號:
您的帳號暱稱:
設定新密碼:
設定新密碼:
×
請輸入要加入的「課程代碼」
請向開設課程的使用者索取「課程代碼」
分類題庫
解題動態
排行榜
討論區
競賽區
登入
註冊
發表新討論
解題報告
#20645: DP + 剪枝
hshua
(hshua)
學校 : 新北市立林口高級中學
編號 : 52506
×
傳送站內訊息
傳給:
主題:
內容:
來源 : [125.228.147.181]
最後登入時間 :
2024-11-19 08:27:35
a192.
接線問題
| From: [220.133.125.66] | 發表日期 : 2020-02-16 11:00
動態規劃DP + (剪枝)
狀態假設:
dp[i][j] 代表{A}長度為 i,{B}長度為 j,且{A}最後一點(i-1)接在{B}的最後一點(j-1) 時的
最小值。
轉移方程:
dp[i][j] = dp[i-1][j-1] + abs(A[i-1] - B[j-1])
因為多筆測資會造成TLE,因此必須進一步剪枝。
觀察在每一次求dp[i][j]時,j 只要計算到 dp 出現最小值即可,之後的點的最小值都會重複,因此可以省略不做(剪枝),用tmin記下最後出現最小值的{B}的長度即可。
調用d[i-1][j-1] 時則以 bmin 為參考,j-1 > bmin 則取最小值 dp[i-1][bmin],否則取 dp[i-1][j-1]。
ZeroJudge Forum