P2123 皇后游戏
ACtheQ
·
·
题解
写一篇清晰的题解，方便捋捋笔者的思路。
这很清晰是一道贪心题目。
我们试着用交换法来证明：
-
首先在这题使用交换法对前面的 C_i 没有影响。
-
每次 C_i 至少比 C_{i-1} 大 B_i，所以 C_i \ge C_{i-1}。
-
可发现单调性，所以使得前面的最小，后面才能尽可能的小。
-
由于交换两个相邻元素更加容易操作，所以使用交换法，并且本题使用交换法是正确的。
这是几个点。
然后开始推式子：
考虑 i 在 i+1 前：
C_i=\max(C_{i-1},\sum ^ {i}_{j=1} a_j)+b_i
C_{i+1}=\max(C_{i},\sum ^ {i+1}_{j=1} a_j)+b_{i+1} = \max(\max(C_{i-1},\sum ^ {i}_{j=1} a_j)+b_i,\sum ^ {i+1}_{j=1} a_j)+b_{i+1}
可以把 b_i,b_{i+1} 带进去。
C_{i+1}= \max(\max(C_{i-1}+b_i+b_{i+1},\sum ^ {i}_{j=1} a_j+b_i+b_{i+1}),\sum ^ {i+1}_{j=1} a_j+b_{i+1})
可以整理出三项的 \max。
C_{i+1}= \max(C_{i-1}+b_i+b_{i+1},\sum ^ {i}_{j=1} a_j+b_i+b_{i+1},\sum ^ {i+1}_{j=1} a_j+b_{i+1})
同理可以得出 i+1 在 i 前的式子。
C_{i+1}= \max(C_{i-1}+b_{i+1}+b_i,\sum ^ {i-1}_{j=1} a_j+a_{i+1}+b_{i+1}+b_i,\sum ^ {i+1}_{j=1} a_j+b_{i})
由于第一项一样所以不影响比大小的结果，所以消掉。（由于方便式子的表达，接下来的式子并不是 C_{i+1} 的值，而是 i 在 i+1 前与 i+1 在 i 前的大小关系。）
C_{i+1}= \max(\sum ^ {i}_{j=1} a_j+b_i+b_{i+1},\sum ^ {i+1}_{j=1} a_j+b_{i+1})
C_{i+1}= \max(\sum ^ {i-1}_{j=1} a_j+a_{i+1}+b_{i+1}+b_i,\sum ^ {i+1}_{j=1} a_j+b_{i})
由于每一项有都带了 \sum ^ {i-1}_{j=1} a_j 所以抵消。
C_{i+1}= \max(a_i+b_i+b_{i+1},a_i+a_{i+1}+b_{i+1})
C_{+1}= \max(a_{i+1}+b_{i+1}+b_i,a_i+a_{i+1}+b_i)
由于都是 a_i,a_{i+1},b_i,b_{i+1} 这四项里面选三项，可以简化成：
C_{i+1}= \max(-a_{i+1},-b_i)
C_{i+1}= \max(-a_i,-b_{i+1})
可以把符号提出去，记得把 \max 变成 \min。
C_{i+1}= -\max(-a_{i+1},-b_i)
C_{i+1}= -\max(-a_i,-b_{i+1})
同样把符号提走：
$\min(a_{i+1},b_i) > \min(a_i,b_{i+1})$ 代表 $i$ 在 $i+1$ 前更优。
接下来说下传递性的问题。
首先设 $g(x,y)$ 为 $x<y$ 成不成立。
- 如果 $g(x,y)$ 成立，那么 $g(y,x)$ 一定不成立
- $g(x,x)$ 不成立
- 如果 $g(x,y),g(y,z)$ 成立，那么 $g(x,z)$ 一定成立（传递性）
这是排序需要的。
拿 $\min$ 来说，当 $a_i$ 与 $a_{i+1}$ 极小时，得不到 $b$ 数组的关系。
没有传递性排不了序，考虑用拓扑序做。
把 $a$ 和 $b$ 数组混在一起做。
设在前头更优的数，连向后头的数。
先排个序，假如最小的是 $a_i$ 那么它连向后面的人，放在最前头。
假如最小的是 $b_i$ 那么后面的人连向它，放在最后头。
同时把另一个 $a_i$ 或 $b_i$ 扔掉，因为位置已经选好了。
然后按照这个顺序 $O(n) $ 统计遍答案就好了！