題解在這裡
優化後的code在這裡
先看這張圖
也就是$j_{k}=j>i=j_{k+1}$
由於$DP[k]$是從$DP[j]$轉移過來而不是$DP[i]$
因此$DP[j]+a+b+c+e+h\geq DP[i]+c+d+e+g+h$
同理
由於$DP[k+1]$是從$DP[i]$轉移過來而不是$DP[j]$
因此$DP[i]+g+h+i\geq DP[j]+b+e+f+h+i$
將上式整理一下
我們得到：
$DP[j]+a+b-d-g\geq DP[i]$
$DP[i]\geq DP[j]+b+e+f-g$
$\Rightarrow DP[j]+a+b-d-g\geq DP[j]+b+e+f-g$
$\Rightarrow a-d\geq e+f$
$\Rightarrow a\geq d+e+f$
可以發現，$\triangle a$和$\triangle def$互為$AA$相似
可是$\triangle a$的對應邊卻比$\triangle def$還短
因此我們得到$a<d+e+f$
矛盾，因此假設錯誤
$j_{k}$不可能$>j_{k+1}$
沒有留言:
張貼留言
歡迎留言或問問題～
若您的留言中包含程式碼，請參考這篇
如果留言不見了請別慌，那是因為被google誤判成垃圾留言，小莫會盡快將其手動還原
注意：只有此網誌的成員可以留言。