[Codeforces g100016B]Command Post (中文：圈地問題) (性質證明)

這題目不好找，附上題目連結

題解在這裡
優化後的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}$