决策单调性与四边形不等式

决策单调性

对于类似于 $F_i = \underset{0\leq j < i}{\min}\{F_j + w(j, i)\}$ 的转移方程，记 $p_i$ 为 $i$ 的最优决策，则若 $p_i$ 单调不减，则乘 $F$ 具有决策单调性。

一维四边形不等式

对于定义在整数集合上的二元函数 $w(x, y)$，若满足对于任意 $a \leq b \leq c \leq d$ 都存在 $w(a, d) + w(b, c) \geq w(a, c) + w(b, d)$，则称 $w$ 满足四边形不等式。

它的另一种等价的表现形式是 $\forall a < b, w(a, b + 1) + w(a + 1, b + 1) \geq w(a, b) + w(a + 1, b + 1)$。

证明：

对于 $a < c$，根据四边形不等式，有 $w(a, c + 1) + w (a + 1, c) \geq w(a, c) + w(a + 1, c + 1)$。

对于 $a + 1 < c$，同样地有 $w(a + 1, c + 1) + w(a + 2, c) \geq w(a + 1, c) + w(a + 2, c + 1)$。

两式相加并化简得到 $w(a, c + 1) + w(a + 2, c) \geq w(a, c) + w(a + 2, c + 1)$。

即对于 $a, a + 2, c, c + 1$ 也满足四边形不等式。依此类推，$\forall a \leq b \leq c$,有 $a,b, c, c + 1$ 满足四边形不等式。这相当于让 $b$ 从 $a$ 开始向右滑动，同理可以使 $d$ 从 $c$ 开始滑动。所以 $a, b, c, d$ 满足四边形不等式。

接着有定理：在上文提到的转移方程中，若 $w$ 满足四边形不等式，则 $F$ 具有决策单调性。

证明：

为了方便，下文记 $p_i$ 为 $p$。

由于 $p$ 为 $i$ 的最优决策，所以对于 $\forall j < p$，有 $F_j + w(j, i) \geq F_p + w(p, i)$。

对于 $i' > i$，根据四边形不等式，有 $w(j, i') + w(p, i) \geq w(j, i) + w(p, i')$。

那么将两式相加即可得到 $F_j + w(j, i') \geq F_p + w(p, i')$，从而得出对于 $i'$，$p$ 一定不劣于 $j$。

因此 $F$ 具有决策单调性。

所以在对于上述转移方程进行转移时，我们可以维护一个 $p$ 数组。

最开始 $p$ 全为 $0$，当我们做完某个 $F_i$ 时应该考虑对于 $j > i$，是否决策 $i$ 优于 $p_j$。换句话说，我们要对于所有能更新的 $j$ 进行更新。

根据决策单调性，一定存在某个分界点 $p$ 使得 $p$ 往后的所有都能使用 $i$ 更新，而 $p$ 往前的所有都不能用 $i$ 更新。所以我们可以使用二分。

具体实现中，我们可以构造一个三元组 $(p, l, r)$，表示对于区间 $[l, r]$ 的最优决策是 $p$。然后维护队列，一开始加入 $(0, 1, n)$。然后每次从队头删除小于当前 $i$ 范围的三元组，从队尾不断访问三元组的 $l$，看 $l$ 是否能被更新，如果可以说明 $l \sim r$ 都可以更新。我们维护一个 $maxr$，然后直接删除队尾。直到访问到某个 $l$ 不能更新，就在 $l \sim r$ 内二分找出 $p$，然后将区间劈成 $[l, p - 1]$ 和 $[p, maxr]$ 即可。

这样做总体的复杂度是 $O(nlogn)$，比原先的 $O(n^2)$ 快很多。

二维四边形不等式

二维四边形不等式用来优化形如 $F_{i, j} = \underset{1\leq k < j}{\min}\{F_{i, k} + F_{k + 1, j} + w(i, j)\}$ 的方程。

在上述转移方程中，如果满足：

$F_{i, i} = w_{i, i} = 0$
$w$ 满足四边形不等式
对于任意 $a \leq b \leq c \leq d$，满足 $w(a, d) \geq w(b, c)$

那么 $F$ 也满足四边形不等式。

证明：

我们考虑数学归纳法。

当 $j - i = 1$ 时，$F_{i, j + 1} + F_{i + 1, j} = F_{i, i + 2} + F_{i + 1, i + 1} = F_{i, i + 2}$。

其中 $F_{i, i + 2}$ 的最优决策可能为 $i$ 或 $i + 1$，我们分别讨论。

若为 $i + 1$，则有 $$ F_{i, i + 2} = F_{i, i + 1} + F_{i + 2, i + 2} + w(i, i + 2) = w(i, i + 1) + w(i, i + 2) \geq w(i, i + 1) + w(i + 1, i + 2) = F_{i, i + 1} + F_{i + 1, i + 2} = F_{i, j} + F_{i + 1, j + 1} $$

若为 $i$，同理可得 $F_{i, i + 2} \geq F_{i + 1, j + 1} + F_{i, j}$。

所以当 $j - i = 1$ 时，$F$ 满足四边形不等式。

接下来我们考虑对于 $j - i = k$ 的情况，假设我们已经证明了 $j - i < k$ 时满足四边形不等式。

假设 $F_{i, j + 1}$ 的最优决策为 $x$，$F_{i + 1, j}$ 的最优决策为 $y$。设 $i + 1\leq x \leq y$。

那么有 $F_{i, j + 1} + F_{i + 1, j} = F_{i, x} + F_{x + 1, j} + w(i, j + 1) + F_{i + 1, y} + F_{y + 1, j} + w(i + 1, j)$

同时 $F_{i, j} + F_{i + 1, j + 1} \leq F_{i, x} + F_{x + 1, j} + w(i, j) + F_{i + 1, y} + F_{y + 1, j + 1} + w(i + 1, j + 1)$

由于 $w$ 满足四边形不等式，所以有 $w(i, j + 1) + w(i + 1, j) \geq w(i + 1, j + 1) + w(i, j)$

根据归纳假设，$F_{x + 1, j + 1} + F_{y + 1, j} \geq F_{x + 1, j} + F_{y + 1, j + 1}$

那么根据以上所有的式子我们可以得到 $F_{i, j + 1} + F_{i + 1, j} \geq F_{i, j} + F_{i + 1, j + 1}$

定理（二维决策单调性）：

在上述转移方程中，我们记 $P_{i, j}$ 为 $F_{i, j}$ 的最优决策，如果 $F$ 满足四边形不等式，则对于任意 $i < j$，有 $P_{i, j - 1} \leq P{i, j} \leq P_{i + 1, j}$。

证明：

下文记 $p$ 为 $P_{i, j}$，同时，由于 $P_{i, j} \leq P_{i + 1, j}$ 和 $P_{i, j - 1} \leq P_{i, j}$ 的证明没有本质的区别，所以我们只证明 $P_{i, j} \leq P_{i + 1, j}$。

要证明 $P_{i, j} \leq P_{i + 1, j}$，则要证明对于 $P_{i + 1, j}$，$p$ 不劣于任何 $k < p$。

对于任意 $k < p$，根据四边形不等式，有 $F_{i, p} + F_{i + 1, k} \geq F_{i, k} + F_{i + 1, p}$。

同时，根据 $p$ 的最优性，$F_{i, k} + F_{k + 1, j} + w(i, j) \geq F_{i, p} + F_{p + 1, j }$。

所以两式相加可得 $F_{i + 1, k} + F_{k + 1, j} \geq F_{i + 1, p} + F_{p + 1, j}$。即对于 $F_{i + 1, j}$ 有 $p$ 比 $k$ 优，所以 $P_{i + 1, j} \geq P_{i, j}$。

同理可得 $P_{i, j - 1} \leq P_{i, j}$，从而原命题得证。

所以我们能够将原本 $O(n^3)$ 的 DP 优化到 $O(n ^ 2)$。

例题

NOI2009 诗人小G

设 $F_i$ 为前 $i$ 句的最小不协调度，$S_i$ 为前 $i$ 句诗的总长度，$a_i$ 为第 $i$ 句诗的长度。

那么显然有 $F_i = \underset{0\leq j < i}{\min}\{F_j + |S_i - S_j + i - j - 1 - L|^P \}$

考虑优化转移，显然其它诸如斜率优化和单调队列都很难优化，因为后面这个 $P$ 次方确实很难受。

那么我们可以思考 $w(j, i) = |S_i - S_j + i - j - 1 - L| ^ P$ 是否满足四边形不等式。

要证明 $w(j, i + 1) + w(j + 1, i) \geq w(j, i) + w(j + 1, i + 1)$，即证明 $w(j + 1, i) - w(j + 1, i + 1) \geq w(j, i) - w(j, i + 1)$。

我们记 $p = (S_i + i) - (S_j + j) - (L + 1), q = (S_i + i) - (S_{j + 1} + j + 1) - (L + 1)$。

那么就要证明 $|q|^P - |q + a_{i + 1} + 1| ^ P \geq |p| ^ P - |p + a_{i + 1} + 1| ^ P$。

设 $f(x) = |x| ^ P - |x + c| ^ P$，因为 $q < p, c > 0$，所以要证明 $f(x)$ 单调递减。

证明这个东西我们可以直接求导，由于同时存在绝对值和次方，所以我们要分 $6$ 种情况讨论。

$P$ 为奇数，$x <= -c$，$f'(x) = -Px^{P - 1} + P(x + c)^{P - 1} < 0$
$P$ 为奇数，$x \in (-c, 0]$，$f'(x) = -Px^{P - 1} - P(x + c)^{P - 1} < 0$
$P$ 为奇数，$x > 0$, $f'(x) = Px^{P - 1} - P(x + c)^{P-1} < 0$

$P$ 为偶数的情况同理，这里就不列举了总之导函数都小于 $0$，所以 $f(x)$ 单调递减，我们就证明了四边形不等式，按照前面提到的方式做即可。

const int N = 100010;
LL T, n, L, P, s[N], g[N];
long double f[N];
int hh, tt;
string str[N];

struct Node {
    int x, l, r;
} q[N];

long double calc(int i, int j) {
    long double ans = 1, val = abs((long double)(s[i] - s[j] + (i - j - 1) - L));
    rep(i, 1, P) ans *= val;
    return f[j] + ans;  
}

void insert(int i) {
    int pos = -1;
    while (hh <= tt) {
        if (calc(q[tt].l, i) <= calc(q[tt].l, q[tt].x)) pos = q[tt --].l;
        else {
            if (calc(q[tt].r, i) < calc(q[tt].r, q[tt].x)) {
                int L = q[tt].l, R = q[tt].r;
                while (L < R) {
                    int mid = L + R >> 1;
                    if (calc(mid, i) > calc(mid, q[tt].x)) L = mid + 1;
                    else R = mid;
                }  
                q[tt].r = L - 1;
                pos = L;
            }
            break;
        }
    }
    if (pos != -1) tt ++, q[tt] = {i, pos, n};  
}

int get(int i) {
    int L = hh, R = tt, ans;
    while (L <= R) {
        int mid = L + R >> 1;
        if (i >= q[mid].l && i <= q[mid].r) {
            ans = mid;
            break;
        }
        if (i <= q[mid].l) R = mid - 1;
        else L = mid + 1;
    }
    return q[ans].x;
}

void solve() {
    n = read(), L = read(), P = read();
    rep(i, 1, n) {
        cin >> str[i];
        s[i] = s[i - 1] + str[i].size();
    }
    hh = 0, tt = 0; 
    q[0] = {0, 1, n}, f[0] = 0; 
    rep(i, 1, n) {
        int j = q[hh].x;
        f[i] = calc(i, j); g[i] = j;
        while (hh <= tt && q[hh].r <= i) hh ++;
        q[hh].l = i + 1;
        insert(i);
    }
    if (f[n] > 1e18) puts("Too hard to arrange");
    else {
        printf("%lld\n", (LL)f[n]);
        vector<string> tmp;
        for (int i = n; i; i = g[i]) {
            string res = "";
            for (int j = g[i] + 1; j <= i; j ++) {
                res += str[j];
                if (j != i) res += ' ';
            }
            tmp.push_back(res);
        }
        for (int i = tmp.size() - 1; i >= 0; i --) cout << tmp[i] << endl;
    }
    puts("--------------------");
}

int main() {   
    T = read();
    while (T --) solve();
    return 0;
}

IOI2000 邮局

先思考朴素 DP 方案。

我们将 $x$ 排序，令 $F_{i, j}$ 为前 $i$ 个村庄有 $j$ 个邮局的最小距离。$w(i, j)$ 表示村庄 $i$ 到村庄 $j$ 之间用一个邮局的最小距离。

那么有 $F_{i, j} = \underset{0 \leq k < i}{\min} \{F_{k, j - 1} + w(k + 1, i) \}$。

其中 $w$ 可以预处理，有 $w(i, j) = w(i, j - 1) + x_j - x_{\frac{i + j}{2}}$。

这样做是 $O(n^2m)$ 的，$n$ 是 $3000$，$m$ 是 $300$，过不了。

状态显然优化不了了，所以考虑优化转移。这个 $w(i, j)$ 并不是很好用其它优化，所以我们考虑四边形不等式。

要证明 $w(i, j + 1) + w(i + 1, j) \geq w(i, j) + w(i + 1, j + 1)$，就要证明 $[w(i, j + 1) - w(i, j)] - [w(i + 1, j + 1) - w(i + 1, j)] \geq 0$。

考虑 $w(i, j + 1) - w(i, j) = w(i, j) + x_{j + 1} - x_{\frac{i + j + 1}{2}} - w(i, j) = x_{j + 1} - x_{\frac{i + j + 1}{2}}$。

同理，$w(i + 1, j + 1) - w(i + 1, j) = x_{j + 1} - x_{\frac{i + j}{2} + 1}$。

所以 $[w(i, j + 1) - w(i, j)] - [w(i + 1, j + 1) - w(i + 1, j)] = x_{\frac{i + j}{2} + 1} - x_{\frac{i + j + 1}{2}} \geq 0$。

从而我们就证明了 $w$ 满足四边形不等式。

接着考虑对于 $ a \leq b \leq c \leq d$，显然有 $w(a, d) \geq w(b, c)$，因为 $a \sim d$ 的范围比 $b \sim c$ 更广。当然这是不严谨的感性理解，证明的话同样可以推一下式子。

然后 $w(i, i)$ 和 $F(i, i)$ 显然都为 $0$，因此我们根据定理得到 $F$ 满足四边形不等式。

const int N = 3010, M = 310;
int n, m;
int x[N], s[N], f[N][M], d[N][N], p[N][N];

int main() {
    n = read(), m = read();
    rep(i, 1, n) x[i] = read();
    sort(x + 1, x + 1 + n);
    rep(i, 1, n) rep(j, i, n) d[i][j] = d[i][j - 1] + abs(x[(i + j) / 2] - x[j]);
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0; 
    rep(j, 1, m) {
        p[n + 1][j] = n;
        fro(i, n, 1) {
            int minn = INF, minp = 0;
            rep(k, p[i][j - 1], p[i + 1][j]) 
                if (minn > f[k][j - 1] + d[k + 1][i]) 
                    minn = f[k][j - 1] + d[k + 1][i], minp = k;
            f[i][j] = minn, p[i][j] = minp;
        }
    }
    printf("%d\n", f[n][m]);
    return 0;
}

posted @ 2025-03-27 07:27 はなこくん阅读(91) 评论(0) 收藏举报

刷新页面返回顶部

比翼鼠の博客

决策单调性与四边形不等式