决策单调性优化——另一种DP优化利器

今天，我们来介绍另一种DP优化方法——决策单调行优化。

决策单调性优化与斜率优化有相似之处，但又有不同之处。 相似之处在于这两者的运用条件都需要满足一个决策如果比另一个决策劣，那么这个决策一定不再是最优决策。不同之处在于，决策单调性优化是为每个决策点分配对应的决策区间，而斜率优化是每个状态自己去寻找相应的决策点。

下面，我们通过一道例题，来深入讲解一下决策单调性优化。

HNOI2008】玩具装箱

（题目图片来源洛谷P3195，侵删）

一种方法

这道题的转移方程还是比较容易写出来的，我们定义f[i]表示前i个玩具装完之后所需要的最小花费，转移方程如下：

转移方程

得到方程后，经过转化可以化成斜率优化的式子（然而它不是今天的主角QAQ），大家可以自己试一试哦。

主角登场

解题过程

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 5;

struct node {
    node() = default;
    node(int _l, int _r, int _id) {
        l = _l; r = _r; id = _id;
    }
    int l, r, id;
}que[N];

long long f[N], sum[N];
int n, l, x, tot, tow;

long long calc(int j, int i) {
    return (f[j] + (sum[i] - sum[j] + i - j - 1- l) * (sum[i] - sum[j] + i - j - 1- l));
}

int find(int l, int r, int i, int j) {
    int mid, ans = r + 1;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (calc(i, mid) > calc(j, mid)) {
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return ans;
}

void solve() {
    que[tot = tow = 1] = node(0, n, 0);
    for (int i = 1; i <= n; ++i) {
        while (que[tot].r < i) tot++;
        f[i] = calc(que[tot].id, i);
        if (tot > tow || calc(i, n) < calc(que[tow].id, n)) {
            while (tot <= tow && calc(i, que[tow].l) < calc(que[tow].id, que[tow].l)) tow--;
            if (tot <= tow) {
                int tmp = find(que[tow].l, que[tow].r, que[tow].id, i);
                que[tow].r = tmp - 1;
                que[++tow] = node(tmp, n, i);
            } else que[++tow] = node(i, n, i);
        }
    }
}

int main () {
    scanf ("%d%d", &n, &l);
    for (int i = 1; i <= n; ++i) {
        scanf ("%lld", &x);
        sum[i] = sum[i - 1] + x;
    }
    solve();
    printf ("%lld\n", f[n]);
    return 0;
}

总结

由于决策单调性优化的程序中无需推导公式（所有的公式推导都是为了证明该问题满足决策单调性），所以在赛场上可以用先猜后证的方法，猜测这道题目满足决策单调性，再用程序证明。

这种做法可以减少思维复杂度，但是要建立在多做题目，有较多经验的基础上，切记不可滥用。

【信息学竞赛从入门到巅峰】，一个专注于分享OI/ACM常用算法及知识的公众号。