没做过 P1080 [NOIP2012 提高组] 国王游戏 的可以去做做（）
这道题的大臣是有全序关系的（就是说可以比较优劣且具有传递性），所以直接定义小于号排序就好了。
以下是我在新建文本文档推导全序关系的过程（英语能理解就行，也不保证推对了，仅供参考）。
let j = i+1, sum = \sum^{i+1}_k a_k, "i < j" means "i is better then j(otherwise, we should swap i and j)"
c_i = max( c_{i-1} , sum - a_j) + b_i
c_{i+1} = max(max(c_{i-1} , sum - a_j) + b_i, sum)+ b_j
c_{i+1} = max( c_{i-1} + b_i + b_j, sum - a_j + b_i + b_j, sum + b_j)
c_{i+1}' = max( c_{i-1} + b_i + b_j, sum - a_i + b_i + b_j, sum + b_i)
i < j ? max(sum - a_j + b_i + b_j, sum + b_j) < max(sum - a_i + b_i + b_j, sum + b_i)
? a_j > b_i ? sum + b_j < sum + b_i or sum + b_j < sum - a_i + b_i + b_j -> a_j > b_i; b_i > min(a_i, b_j)
: b_i + b_j - a_i < b_i or b_i + b_j - a_i < - a_j + b_i + b_j -> a_j < b_i; a_j > min(a_i, b_j).
-> min(a_i, b_j) < min(a_j, b_i)
if min(a_j, b_k) < min(a_k, b_j)
is min(a_i, b_k) < min(a_k, b_i) true?
min(a, b) < min(c, d) -> a < c, d or b < c, d
min(c, e) < min(f, b) -> c < b, f or e < b, f
then we want to know is min(a, e) < min(f, d) true?
-> a < d, f or e < d, f -> it's true, let us prove it
if a < d, f or e < d, f is false,
let a < c, d. then if c < b, f -> a < c < d, f. wrong
so e < b, f. then we have f < a < d < e < f -> f < f. wrong
we ignore something important(the quality).
if min(a_i, b_j) = min(a_j, b_i) then i = j? nope.
consider {1, 1} = {2, 7} < {3, 5} but {1, 1} = {3, 5}
let a_i = min(a_i, b_j)
notice that if a_i = a_j. i < j iff b_i > b_j
otherwise a_i = b_i, i<j or i is j
标签：游戏,推导,min,max,sum,P2123,let,true From： https://www.cnblogs.com/Lcyanstars/p/16614751.html