「BZOJ 3156」防御准备 - 斜率优化 DP

我们定义战线为一条长度为 的序列，在这条战线上共设有 个检查点，从左到右依次标号为 到 。一个战线为合法战线当且仅当任意一个检查点可以通过安全检查。对于第 个点，通过安全检查的方法有两种，第一种是放置一个守卫塔，这将花费 的费用，第二种方式是放置一个木偶，放置木偶的花费等于这个检查点右侧的第一个守卫塔到它的距离。第 个点只能放置守卫塔。求最小的战线花费值。

链接

BZOJ 3156

题解

将整个序列反转，放置木偶的花费等于这个检查点左侧的第一个守卫塔到它的距离，一号检查点必须放置守卫塔。

设 表示前 个检查点通过检查的最小代价，枚举 ，在 位置放置一个守卫塔，之后一直到 的位置全部放置木偶。

斜率优化，考虑两个决策 、（），若 比 优，则有

维护决策点，使斜率递增，最优决策取队首。时间复杂度为 。

代码

#include <cstdio>
#include <climits>
#include <algorithm>

const int MAXN = 1000000;

int n;
long long c[MAXN + 1], f[MAXN + 1];

inline void prepare() {
    std::reverse(c + 1, c + n + 1);
}

/*
inline void force() {
    std::fill(f, f + n + 1, LLONG_MAX);
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        int _j = -1;
        for (int j = 0; j < i; j++) {
            if (f[i] > f[j] + c[j + 1] + (i - j - 1) * (i - j) / 2) {
                f[i] = f[j] + c[j + 1] + (i - j - 1) * (i - j) / 2;
                _j = j;
            }
        }

        printf("%d --> %d\n", i, _j);
    }
}
*/

template <typename T> inline T sqr(const T &x) { return x * x; }

inline double x(const int i) { return f[i] + c[i + 1] + sqr(static_cast<long long>(i)) * 0.5 + i * 0.5; }

inline double slope(const int a, const int b) {
    return double(x(a) - x(b))
         / double(a - b);
}

inline void dp() {
    std::fill(f, f + n + 1, LLONG_MAX);
    f[0] = 0;

    static int q[MAXN];
    int *l = q, *r = q;
    *r = 0;

    for (int i = 1; i <= n; i++) {
        while (l < r && slope(*(l + 1), *l) < i) l++;

        int &j = *l;
        f[i] = f[j] + c[j + 1] + (i - j - 1) * (i - j) / 2;
        // printf("%d --> %d\n", i, j);

        if (i < n) {
            while (l < r && slope(*r, *(r - 1)) > slope(i, *r)) r--;
            *++r = i;
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &c[i]);

    prepare();

    // force();
    dp();
    printf("%lld\n", f[n]);

    return 0;
}