决策单调性

定义1: $f(i)$

在一个数轴上$1 \leqslant j< i$,有一个函数$G(j,i)$,表示$j$对$i$的贡献,其中最优值,称为$f(i)$.

定义2: 决策单调性

对于$1 \leqslant j< i < x < y$,若$G(i,x)$优于$G(j,i)$,那么对于$y > x$,都有$G(i,y)$ 优于 $G(j,y)$。

另一种说法: 若$i$对于$x$的贡献优于$j$对于$x$的贡献且$j < i$,那么对于任意的$y>x$,$i$对于$y$的贡献也优于$j$对于$y$的贡献。这种性质我们称为决策单调性。

推论1: $p[x]$ 存在性

对于$i \in [1,x-1]$,其中使得$G(i,x)$最优的点$i$为最优决策点。记此时的最优$G(i,x)$值为$f(x)$. 可以想到最优决策点必然存在.

那么设$p[x]$表示最优$G(i,x)$的$i$值,也称$x$的决策点,记$p[x] = i$

推论2: 决策点数组单调不减

若$G(i,x)$满足决策单调性, 那么$p$数组是单调不减的,即

1. 任意两个相邻值,满足: $p[x] \leqslant p[x+1]$。
2. 任意两个值$x,y$,$x < y \Rightarrow p[x] \leqslant p[y]$

推论3: 决策点后续影响

对于每一个决策点$a$,都有一个区间$[i,j]$或空集,使得$x \in [i,j]$时,$p(x)$的决策点都是$a$.这些区间的任意两个不会相交(这个应该是不对的,应该可以相交,当有多个点都是最优决策点的时候.)

推论4: 决策点后续影响具有二分性

对于每一个决策点$a$,都有一个区间$[i,j]$或空集,使得$x \in [i,j]$时,$p(x)$的决策点都是$a$.这些区间的任意两个不会相交(这个应该是不对的,应该可以相交,当有多个点都是最优决策点的时候.)