[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}$是不可能的