2016年2月22日 星期一

[Codeforces 321E]Ciel and Gondolas (中文:搭車問題) (性質證明)

題解在這裡
如果想看最終的code,請參考這裡

首先,這個性質是,假設
$N$個人分配在$C$車的最佳分法是$1\sim a_{1}$在第一車、$a_{1}+1\sim a_{2}$在第二車、$a_{2}+1\sim a_{3}$在第三車......$a_{C-1}+1\sim N$在第$C$車
$M$個人分配在$C$車的最佳分法是$1\sim b_{1}$在第一車、$b_{1}+1\sim b_{2}$在第二車、$b_{2}+1\sim b_{3}$在第三車......$b_{C-1}+1\sim M$在第$C$車

當$N\leq M$時,我們有$a_{k}\leq b_{k},1\leq k\leq C-1$

可以發現,我們只須證明$a_{C-1}\leq b_{C-1}$
然後剩餘的推導就迎刃而解了

為甚麼呢?
由於$a_{C-1}\leq b_{C-1}$,因此問題轉換成了要證明:
$a_{C-1}$個人分配在$C-1$車的最佳分法是......
$b_{C-1}$個人分配在$C-1$車的最佳分法是......
可以發現,將數字代換一下:
$a_{C-1}\rightarrow N$
$b_{C-1}\rightarrow M$
$C-1\rightarrow C$
又回到原問題的證明了,只是$C$少了$1$!

當然,$C=1$的時候這個性質顯然是成立的

現在,我們要做的就是證明$a_{C-1}\leq b_{C-1}$
我們先來看這張圖,圖中$N*N$的正方形就是題目給你的陌生程度矩陣:
我們把上面的這張圖的右下角放大
現在我們算完了綠色部分,打算擴展到淺藍色邊界
如下圖,我們來證明藍色的選擇一定比橘色的選擇還要好
其中$i<j<k$,$a,b,c,d,e,f,g$代表對應區域內的數字總和
令$DP[i]$為前$i$個人分配到$C$車的最小陌生程度
我們已經算好$DP[k]=DP[j]+e$,現在要來決定$DP[k+1]$

假設橘色選法比藍色選法還要好
這樣我們就有$DP[i]+a+b+c+d+e+f+g<DP[j]+e+g$
因為綠色部分是$DP[k]$的最佳解之一,因此我們有$DP[j]+e\leq DP[i]+a+b+d+e$
將兩個式子整理一下,我們會得到以下推導:
$DP[i]+a+b+c+d+f<DP[j]\leq DP[i]+a+b+d$
$\Rightarrow DP[i]+c+f<DP[i]$
$\Rightarrow c+f<0$
怎麼可能?!$c+f$明明就是某個面積下的數字總和啊,一定得是正數或$0$
矛盾,得證

$a_{C-1}$對應到上面的$j$
$b_{C-1}$對應到上面的$i$
因此強迫$b_{C-1}<a_{C-1}$是不可能的

沒有留言:

張貼留言

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