当前位置：首页 > news >正文

[HNOI2008]玩具装箱toy

news 来源：原创 2024/4/24 10:05:38

Description

BZOJ1010

Solution

斜率优化DP首题，多写一点吧。

Step 1 写出DP方程

设\(f_i\)为\(i\)点时的最优方案，\(s_i\)为\(i\)点\(C_i\)前缀和，则有\(f_i = min\{f_j+(i-j-1+s_i-s_j-l)^2\mid 0\le j < i-1\}\)。

Step 2 证明决策单调性

不要被这个“决策单调性”给唬住，其实就是证明：若在计算\(f_i\)的时候，选\(j\)比选\(k\)好，那么之后永远都有选\(j\)比选\(k\)好。

证明：
首先设\(t_x = s_x+x,c = l+1\)且\(j > k\)，选\(j\)比选\(k\)好，简化之后的表示
\(f_j+(t_i-t_j-c)^2 < f_k + (t_i-t_j-c)^2\)
\(\Leftrightarrow f_j+t_i^2+t_j^2+c^2-2t_it_j+2t_jc-2t_ic < f_k+t_i^2+t_k^2+c^2-2t_it_k+2t_kc-2t_ic\)
\(\Leftrightarrow f_j+t_j^2-2t_it_j+2t_jc - f_k - t_k^2 + 2t_it_k - 2t_kc < 0\)
\(\Leftrightarrow f_j + t_j^2+ 2t_jc - f_k - t_k^2 - 2t_kc < 2t_it_j - 2t_it_k\)
由于\(t\)是单调上升的，所以\(2t_j-2t_k>0\)，所以
\(\mbox{原式}\Leftrightarrow \displaystyle\frac{f_j + t_j^2+ 2t_jc - f_k - t_k^2 - 2t_kc}{2t_j - 2t_k} < t_i\)
又因为\(t\)是单调上升的，所以一旦满足了这个条件，选\(j\)永远比选\(k\)好。

Step 3 构造斜率形式

这一步其实就是看分子分母，化出和\(j\)，\(k\)有关的式子，就可以了。

设\(F_x = t_x^2+f_x+2ct_x\)，\(G_x=2t_x\)
则原式可化成\(\displaystyle\frac{F_j-F_k}{G_j-G_k}<t_i\)，由于\(G\)单调增，不等号左边的式子（上下同乘\(-1\)后）就是在平面\(GOF\)上的一条直线\((k,j)\)的斜率（记为\(K_{k,j}\)）。

Step 4 证明斜率单调

设\(x, y, z\)满足\(x < y < z\)，且\(K_{x,y}>K_{y,z}\)，则选\(y\)不可能更优。

证明：考虑反证法，若\(y\)优于\(x\)和\(z\)，则有：
\(\displaystyle\frac{F_z-F_y}{G_z-G_y}>t_i\)（这个式子其实是将Step2中的\(j>k\)反过来推出来的）
和\(\displaystyle\frac{F_y-F_x}{G_y-G_x}<t_i\)
即\(K_{y,z}=\displaystyle\frac{F_z-F_y}{G_z-G_y}>\displaystyle\frac{F_y-F_x}{G_y-G_x}=K_{x,y}\)与题设矛盾。

这里应该先考虑\(y\)优于\(x\)和\(z\)，推出式子后得出斜率的单调结论。

Step 5 单调队列优化DP

单调队列是一个双端队列。

由于Step2,3，若在\(i\)处有\(K_{k,j}<t_i\)(\(k, j\)位于队首)，则应该令\(k\)出队，反复执行直至队列中只有一个元素或不满足条件为止，此时队首即为决策。

当计算出\(f_i\)后，利用Step4的结论，在队尾不断出队直至直至队列中只有一个元素或不满足条件为止，并将\(i\)放入队尾。

Code

#include <cstdio>
#include <cmath>

typedef long long LL;
const int N = 50000 + 10;
const double eps = 1e-10;

int n, l;
LL C[N], f[N], s[N], t[N], c, F[N], G[N];
int q[N], qhd, qtl;

inline double K(int x, int y) {
    return 1.0 * (F[x] - F[y]) / (G[x] - G[y]); 
}

inline int dcmp(double x) {
    if (fabs(x) < eps) return 0;
    else if (x < 0) return -1;
    else return 1;
}

int main () {
    // input
    scanf("%d%d", &n, &l);
    for (int i = 1; i <= n; ++i) scanf("%lld", &C[i]);
    // init
    c = l + 1;
    for (int i = 1; i <= n; ++i) {
        s[i] = s[i-1] + C[i];
        t[i] = s[i] + i;
        G[i] = 2 * t[i];
    }
    // dp 
    f[0] = 0;
    q[qtl++] = 0;
    for (int i = 1; i <= n; ++i) {
        while (qhd < qtl - 1) {
            if (dcmp(K(q[qhd], q[qhd+1]) - t[i]) == -1) qhd++;
            else break;
        }
        int j = q[qhd];
        f[i] = f[j] + (t[i] - t[j] - c) * (t[i] - t[j] - c);
        F[i] = t[i] * t[i] + f[i] + 2 * c * t[i];  // mark
        while (qhd < qtl - 1) {
            if (dcmp(K(q[qtl-1], q[qtl-2]) - K(q[qtl-1], i)) == 1) qtl--;
            else break;
        }
        q[qtl++] = i;
    }   
    printf("%lld\n", f[n]);
    return 0;
}