#20645: DP + 剪枝


hshua (hshua)

學校 : 新北市立林口高級中學
編號 : 52506
來源 : [125.228.147.181]
最後登入時間 :
2024-11-10 13:26:19
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