题解 P3195 【[HNOI2008]玩具装箱TOY】

· · 题解

容易推出，如果玩具长度的前缀和为sum[]，那么DP方程为：

解法一：决策单调性。 可以看出原方程是一个$f[i]=min{0<=j<i,f[j]+w(i,j)}$的模型，其中$w(i,j)=(i-j-1-L+sum[i]-sum[j])^2$。 设$X=i-j-1-L+sum[i]-sum[j]$，则： $w(i+1,j+1)=(X+c[i+1]-c[j+1])^2 w(i+1,j)=(X+c[i+1]+1)^2 w(i,j+1)=(X-c[j+1]-1)^2

此时w(i,j)+w(i+1,j+1)=2X^2+2c[i+1]X-2c[j+1]X+c[i+1]^2-2c[i+1]c[j+1]+c[j+1]^2

w(i+1,j)+w(i,j+1)=2X^2+2c[i+1]X-2c[j+1]X+c[i+1]^2+2c[i+1]+2c[j+1]+c[j+1]^2+2

可得w(i,j)+w(i+1,j+1)<=w(i+1,j)+w(i,j+1)，即满足决策单调性。

决策单调性实现即，用一个栈维护每个决策的起始和结束位置。对于每个已经计算出来的f[i]，去寻找它能更新的状态有哪些。

具体为：

（1）在栈顶的决策起始位置判断起始位置是否决策i更优。如果是，则退栈，继续执行（1）。否则转（2）。

（2）二分查找在栈顶的决策区间里，决策i最优的最左位置pos，把栈顶的决策结束位置设为pos-1，并把决策i压入栈，决策起始位置为pos，结束位置为n（但是如果pos>n就不要入栈，我就在这里调了好久）。

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
typedef long long ll;
const int N = 5e4 + 5;
int n, L, c[N], top; ll sm[N], f[N];
struct cyx {
    int l, r, x;
    cyx() {}
    cyx(int _l, int _r, int _x) :
        l(_l), r(_r), x(_x) {}
} stk[N];
ll w(int i, int j) {
    ll res = sm[j] - sm[i] - L;
    res += j - i - 1; return res * res;
}
int findx(int i) {
    int l = stk[top].l, r = stk[top].r, mid;
    while (l <= r) { // 二分查找新决策的起始位置
        mid = l + r >> 1;
        if (f[i] + w(i, mid) < f[stk[top].x] + w(stk[top].x, mid))
            r = mid - 1;
        else l = mid + 1;
    }
    return l;
}
int main() {
    int i, now = 1; n = read(); L = read();
    for (i = 1; i <= n; i++) c[i] = read(),
        sm[i] = sm[i - 1] + c[i];
    stk[top = 1] = cyx(1, n, 0);
    for (i = 1; i <= n; i++) {
        f[i] = f[stk[now].x] + w(stk[now].x, i);
        while (i < stk[top].l && f[i] + w(i, stk[top].l) < f[stk[top].x] +
            w(stk[top].x, stk[top].l)) top--;
        int u = findx(i); stk[top].r = u - 1;
        if (u <= n) stk[++top] = cyx(u, n, i);
        if (i == stk[now].r) now++;
    }
    cout << f[n] << endl;
    return 0;
}

时间复杂度O(nlogn)。

解法二：斜率优化。

可以发现原方程为

f[i]=min{0<=j<i,f[j]+((i+sum[i]-L-1)-(sum[j]+j))^2}

设a[i]=i+sum[i]-L-1，b[j]=sum[j]+j，

则f[i]=min{0<=j<i,f[j]+(a[i]-b[j])^2}

即f[i]=min{0<=j<i,f[j]+b[j]^2-2a[i]b[j]}+a[i]^2

再设X[j]=b[j]，Y[j]=f[j]+b[j]^2，

则可以发现a[]和X[]都单调递增，所以斜率是单调递减的。用单调队列维护凸壳，每次从队首不断出队以找出最优决策。

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
typedef long long ll;
const int N = 5e4 + 5;
int n, H, T, L, que[N];
ll f[N], a[N], b[N], X[N], Y[N];
bool check(int p1, int p2, int p3) {
    return (X[p2] - X[p3]) * (Y[p1] - Y[p3]) - (X[p1] - X[p3])
        * (Y[p2] - Y[p3]) >= 0; // 根据叉积判断p1p2的斜率是否大于p2p3的斜率
}
ll calc(int x, int y) {
    return f[x] + b[x] * b[x] - 2ll * a[y] * b[x];
}
int main() {
    int i; n = read(); L = read(); H = T = 1;
    for (i = 1; i <= n; i++) {
        b[i] = b[i - 1] + read() + 1;
        a[i] = b[i] - L - 1;
    }
    for (i = 1; i <= n; i++) {
        while (H < T && calc(que[H], i) >= calc(que[H + 1], i)) H++;
        f[i] = calc(que[H], i) + a[i] * a[i];
        X[i] = b[i]; Y[i] = f[i] + b[i] * b[i];
        while (H < T && check(que[T - 1], que[T], i)) T--;
        que[++T] = i;
    }
    cout << f[n] << endl;
    return 0;
}

时间复杂度O(n)。