2016年3月8日 星期二

[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}$

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原