算法简介

例题引入

题目来源

NOIP2012提高组D1T2 国王游戏

使用邻项交换排序需要注意的问题

另一道例题

题目描述

$$c_i=\begin{cases}a_1+b_1 & i=1\\\max(c_{i-1},\sum\limits_{j=1}^ia_j)+b_i & 2\le i\le n\end{cases}$$

严格弱序

严格弱序简介

1. $x\not<x$ （非自反性）
2. 若 $x<y$，则 $y\not<x$ （非对称性）
3. 若 $x<y,y<z$，则 $x<z$ （传递性）
4. 若 $x\not<y,y\not<x,y\not<z,z\not<y$，则 $x\not<z,z\not<x$ （不可比性的传递性）

1. It has to be antisymmetric.

This means that for operator $<$: If $x < y$ is true, then $y < x$ is false.

This means that for a predicate op(): If op(x,y) is true, then op(y,x) is false.

2. It has to be transitive.

This means that for operator $<$: If $x < y$ is true and $y < z$ is true, then $x < z$ is true.

This means that for a predicate op(): If op(x,y) is true and op(y,z) is true, then op(x,z)

is true.

3. It has to be irreflexive.

This means that for operator $<$: $x < x$ is always false.

This means that for a predicate op(): op(x,x) is always false.

4. It has to have transitivity of equivalence, which means roughly: If a is equivalent to b and b is

equivalent to c, then a is equivalent to c.

This means that for operator $<$: If $!(a<b) \&\& !(b<a)$ is true and $!(b<c) \&\& !(c<b)$ is true

then $!(a<c) \&\& !(c<a)$ is true.

This means that for a predicate op(): If op(a,b), op(b,a), op(b,c), and op(c,b) all yield

false, then op(a,c) and op(c,a) yield false.

满足传递性的证明

$\forall \begin{cases}\,(a_i<a_j\lor b_j<a_j)\land(a_i<b_i\lor b_j<b_i) \\\,(a_j<a_k\lor b_k<a_k)\land(a_j<b_j\lor b_k<b_j)\end{cases}$，有 $(a_i<a_k\lor b_k<a_k)\land(a_i<b_i\lor b_k<b_i)$。

不具有不可比性的传递性的证明

$$\begin{array}{c|c|c}&a&b\\i&3&5\\j&1&1\\k&2&7\end{array}$$

$\begin{cases}\min(3,1)=\min(1,5)\\\min(1,7)=\min(2,1)\end{cases}$，但 $\min(3,7)\ne \min(2,5)$。

正确解法

一个解法是否正确的判断方式

1. 满足严格弱序。

2. $\forall P_{i,j}=true$，$\min(a_i,b_j)\le\min(a_j,b_i)$ 。