「HNOI2008」玩具装箱 - 斜率优化 DP

发表于 | 分类于

P 教授有编号为 ~ 的 件玩具，第 件玩具经过压缩后变成一维长度为 。为了方便整理，P 教授要求在一个一维容器中的玩具编号是连续的。如果将第 件玩具到第 个玩具放到一个容器中，那么容器的长度将为 。如果容器长度为 。其制作费用为 。其中 是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容 器，甚至超过 。但他希望费用最小。

链接

BZOJ 1010
CodeVS 1319
COGS 1330

题解

动态规划，设 表示前 i 件玩具放进若干个容器中的最小费用，前缀和 。

转移时枚举前面多少个装在同一个箱子里，设它为 ，则第 ~ 个装在同一个箱子里，长度为 ，即

直接计算的复杂度为 ，超时，考虑优化。

设 ，，上面的方程可以转化为

考虑两个决策 和 （），若 a 比 b 优，当且仅当

左边成为了斜率的形式，三个式子都是单调的，因此可以用一个单调队列维护每个决策，保证最优决策在队首，两两决策点形成的斜率递增，每次状态转移复杂度降为 ，总时间复杂度为 。

代码

#include <cstdio>

const int MAXN = 50000;

int n, L, a[MAXN];
long long s[MAXN + 1], f[MAXN + 1];

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

inline long long g(const int i) { return s[i] + i - L - 1; }
inline long long h(const int j) { return s[j] + j; }

inline double slope(const int a, const int b) {
    return double((f[a] + sqr(h(a))) - (f[b] + sqr(h(b)))) / double(h(a) - h(b));
}

int main() {
    scanf("%d %d", &n, &L);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i - 1];

    static long long q[MAXN];
    long long *l = q, *r = q - 1;
    *++r = 0;

    for (int i = 1; i <= n; i++) {
        while (l < r && slope(*(l + 1), *l) <= 2 * g(i)) l++;
        f[i] = f[*l] + sqr(g(i) - h(*l));
        while (l < r && slope(*r, *(r - 1)) > slope(i, *r)) r--;
        *++r = i;
    }

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

    return 0;
}