bzoj 1010

[HNOI2008]玩具装箱toy

题解

设 $dp[i]$ 表示考虑到第 $i$ 件物品时的最小花费，则

$dp[i] = \min_{0 \le j < i}\{dp[j] + (i - j - 1 + \sum_{k=j+1}^{i}c[k] - L) ^ 2\}$

令 $s[i] = \sum_{k = 1}^{i}{c[k]}$ ， $f[i] = i + s[i]$ ， $A = L + 1$ ，则

$\begin{aligned} dp[i] =& \min_{0 \le j < i}\{dp[j] + (f[i] - f[j] - A)^2\} \\ =& \min_{0 \le j < i}\{-2(f[j]+A)\cdot{}f[i] + dp[j] + (f[j]+A)^2\} + f[i]^2 \end{aligned}$

令 $k_i = -2(f[i] + A), b_i = dp[i] + (f[i]+A)^2$ ，则

$dp[i] = \min_{0 \le j < i}\{k_j \cdot f[i] + b_j\} + f[i]^2$

显然 $k_i$ 是随着 $i$ 单调减少的，并且 $f[i]$ 随 $i$ 单调增. 单调队列维护一个 $\{l|l: y = k_i x + b_i\}$ 的上凸壳即可.

略微有点爆 long long，用 long double 水过去了.

代码

#include <cstdio>
#include <cmath>

using namespace std;

typedef long double ll;

const int maxn = 50050;

ll k[maxn], b[maxn];
inline ll g(int i, ll x)
{
    return k[i] * x + b[i];
}
/* if i is above s & j */
bool above(int s, int i, int j)
{
    ll l = (b[i] - b[s]) * (k[s] - k[j]);
    ll r = (b[j] - b[s]) * (k[s] - k[i]);
    return (l >= r);
}

int N;
ll L;
ll s[maxn];
ll f[maxn], dp[maxn];
int ql, qr, q[maxn];

inline void calc(int i)
{
    ll t = f[i] + L;
    k[i] = -2ll * t;
    b[i] = dp[i] + t * t;
}

int main(void)
{
    int i;
    scanf("%d%Lf", &N, &L); L++;
    for (i = 1; i <= N; i++)
    {
        scanf("%Lf", s + i);
        s[i] += s[i-1];
        f[i] = i + s[i];
    }
    ql = qr = dp[0] = 0;
    calc(0); q[qr++] = 0;
    for (i = 1; i <= N; i++)
    {
        while (ql + 1 < qr && g(q[ql], f[i]) >= g(q[ql + 1], f[i])) ql++;
        dp[i] = g(q[ql], f[i]) + f[i] * f[i];
        calc(i);
        while (ql + 1 < qr && above(q[qr - 2], q[qr - 1], i)) qr--;
        q[qr++] = i;
    }
    printf("%lld\n", (long long)round(dp[N]));
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

# bzoj 1010

# [HNOI2008]玩具装箱toy

# 题解

# 代码

bzoj 1010

[HNOI2008]玩具装箱toy

题解

代码