题解 P2123 【皇后游戏】

### 前言 此题的关键就是证明对于两位大臣$i,j$，如果$min(a_i,b_j)\le min(a_j,b_i)$，那么我们将$i$放在前面更优。 由于笔者认为大部分题解对于上述结论的证明都是大同小异或是一带而过，故此处给出上述结论的一种不同的证明方式，后续处理其余题解已经讲得很清楚，故此处不再赘述。 ### 正题 [传送门](https://www.luogu.org/problem/P2123) 解析：题目要求的是这样一个式子中$c[i]$的最大值的最小值：  由于$a_i,b_i$均为正数，所以$c_i$一定是递增的，故我们要求的即为$c_n$的最小值。 我们有一个结论：对于两位大臣$(a_i,b_i),(a_j,b_j)$，如果$min(a_i,b_j)\le min(a_j,b_i)$，那么我们将$(a_i,b_i)$放在前面更优，证明如下： $$c_1=a_1+b_1$$ $$c_2=max(c_1,a_1+a_2)+b_1=max(a_1+b_1,a_1+a_2)+b_2$$ $$c_2=max(a_1+b_1+b_2,a_1+a_2+b_2)$$ $$c_3=max(c_2,a_1+a_2+a_3)+b_3$$ $$c_3=max(a_1+b_1+b_2,a_1+a_2+b_2,a_1+a_2+a_3)+b_3$$ $$c_3=max(a_1+b_1+b_2+b_3,a_1+a_2+b_2+b_3,a_1+a_2+a_3+b_3)$$ 综上，我们可以发现一个规律： 我们记$S_n(k)$为$\sum_{i=1}^ka_i+\sum_{i=k}^nb_i$ 那么$c_i=max(S_i(1),S_i(2),S_i(3),...,S_i(i))$ 但这只是我们找出来的规律，下面给出严谨证明： 我们考虑用一个$2*n$的矩阵来表示我们的序列$(a_1,b_1),(a_2,b_2),...,(a_n,b_n)$ 以$c_3$为例，我们来画出这些走法，它们分别对应所有的$S_3$：  所以$c_n$在我们的矩阵里表示从$a_1$到$b_n$的$n$条路径中$n+1$个数字和的最大值。 我们用数学归纳法证明$c_i=max(S_i(1),S_i(2),S_i(3),...,S_i(i))$： 当$n=1$时，$c_1=max(S_1(1))$，显然成立。 假设当$n=k(k\ge1)$时，命题成立，即$c_k=max(S_k(1),S_k(2),S_k(3),...,S_k(k))$ 那么当$n=k+1$时， $$c_{k+1}=max(c_k,a_1+a_2+...+a_{k+1})+b_{k+1}$$ 将$b_{k+1}$带入$max$中 $$c_{k+1}=max(c_k+b_{k+1},a_1+a_2+...+a_{k+1}+b_{k+1})$$ 合并后面的项 $$c_{k+1}=max(c_k+b_{k+1},S_{k+1}(k+1))$$ 将$c_k$拆开 $$c_{k+1}=max(S_k(1)+b_{k+1},S_k(2)+b_{k+1},...,S_k(k)+b_{k+1},S_{k+1}(k+1))$$ 按照$S$的定义合并所有项 $$c_{k+1}=max(S_{k+1}(1),S_{k+1}(2),...,S_{k+1}(k+1))$$ 原命题得证。 下一步，我们来证明如果$min(a_i,b_j)\le min(a_j,b_i)$，那么我们将$(a_i,b_i)$放在前面更优。 考虑上文提到的矩阵，我们对于一个矩阵 $$ \begin{bmatrix} a_1 & a_2 &a_3 &...&a_n\\\\ b_1 & b_2&b_3&...&b_n \end{bmatrix} $$ 我们如果调换两人的顺序，也就是调换矩阵中两列的顺序。 我们假设调换第$k$列和第$k+1$列，我们得到一个新矩阵 $$ \begin{bmatrix} a_1' & a_2' &a_3' &...&a_n'\\\\ b_1' & b_2'&b_3'&...&b_n' \end{bmatrix} $$ 其中 $$ \begin{bmatrix} a_i \\\\ b_i \end{bmatrix}=\begin{bmatrix} a_i' \\\\ b_i' \end{bmatrix}\quad(1\le i\le n,i≠k,i≠k+1) $$ $$ \begin{bmatrix} a_k \\\\ b_k \end{bmatrix}=\begin{bmatrix} a_{k+1}' \\\\ b_{k+1}' \end{bmatrix}\quad $$ $$ \begin{bmatrix} a_{k+1} \\\\ b_{k+1} \end{bmatrix}=\begin{bmatrix} a_{k}' \\\\ b_{k}' \end{bmatrix}\quad $$ 我们记$S_n'(k)$为$\sum_{i=1}^ka_i'+\sum_{i=k}^nb_i',c'_n=max(S_n'(1),S_n'(2),...,S_n'(n))$ 我们设$\sigma=S_n(k-1)=S_n'(k-1)=\sum_{i=1}^{k-1}a_i+\sum_{i=k+2}^{n}b_i=\sum_{i=1}^{k-1}a_i'+\sum_{i=k+2}^{n}b_i'$，那么我们有： $$S_n(k)=\sigma+a_k+b_k+b_{k+1}$$ $$S_n(k+1)=\sigma+a_k+a_{k+1}+b_{k+1}$$ $$S_n'(k)=\sigma+a_k'+b_k'+b_{k+1}'=\sigma+a_{k+1}+b_{k+1}+b_k$$ $$S_n'(k+1)=\sigma+a_k'+a_{k+1}'+b_{k+1}'=\sigma+a_{k+1}+a_k+b_k$$ 记$m=min(a_k,a_{k+1},b_k,b_{k+1}),M=max(S_n(k),S_n(k+1),S_n'(k),S_n'(k+1))$ 我们分别讨论$m$的取值， 当$m=a_k$时，依照上文推出的$S,S'$的表达式，$M=S_n'(k)$，所以$max(S'_n(k),S_n'(k+1))\ge max(S_n(k),S_n(k+1))$，即$c_n'\ge c_n$ 其余三种情况同理。 最后我们得出当$m=a_k$或$b_{k+1}$时，$c_n\le c_n'$，所以不应交换。 当$m=a_{k+1}$或$b_k$时，$c_n\ge c_n'$，此时应交换$k$与$k+1$两列。 证毕。