BZOJ 1911. [Apio2010]特别行动队

Brief description:

略。)

Analysis:

记代价函数 $$!w(x) = ax^2 + bx + c$$

然后:

$$! \begin{aligned} f_i &= \min_{0 \leq j < i}\big\{ f_j + w(s_i-s_j)\big\} \\ &= \min_{0 \leq j < i}\big\{ f_j + as_j^2 - bs_j -2as_is_j\big\} + w(s_i) \end{aligned}$$ 写成斜率优化的标准形式,b = kx + y 这里有:

  • $$k = -2as_i$$
  • $$x = s_j $$
  • $$y = f_j + as_j^2 – bs_j $$

这里 $$x$$ 和 $$k$$ 均单调(因为 $$s_i$$ 单调),单调队列即可。

//}/* .................................................................................................................................. */

const int N = int(1e6) + 9;
LL f[N], s[N], a, b, c; int q[N], cz, op;
int n;

LL det(LL x1, LL y1, LL x2, LL y2){
    return x1*y2 - x2*y1;
}

#define k (-2*a*s[i])
#define x(j) (s[j])
#define y(j) (f[j]+a*sqr(x(j)) - b*(x(j)))
#define eval(j) (k*x(j)+y(j))

int dett(int p0, int p1, int p2){
    LL t = det(x(p1)-x(p0), y(p1)-y(p0), x(p2)-x(p0), y(p2)-y(p0));
    return t < 0 ? -1 : t > 0;
}

LL w(LL x){
    return a*x*x+b*x+c;
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n); RDD(a, b, c); REP_1(i, n) s[i] = s[i-1] + RD();

    cz = 0, op = 0; REP_1(i, n){
        while (cz < op && eval(q[cz]) <= eval(q[cz+1])) ++cz; f[i] = eval(q[cz]) + w(s[i]);
        while (cz < op && dett(q[op-1], q[op], i) >= 0) --op; q[++op] = i;
    }

    OT(f[n]);
}

BZOJ 1010. [HNOI2008]玩具装箱toy

Brief description:

略。)

Analysis:

首先写好暴力。

$$! f_i = \min_{0 <= j < i}\big\{ f_j + (i-j+s_i-s_{j-1}-L)^2 | j < i\big\} $$ 观察,微调,分离常数。 [cpp] REP_1(i, n) s[i] += i; ++L; [/cpp] $$! \begin{aligned} f_i &= \min_{0 \leq j < i}\big\{ f_j + ((s_i-L)-s_j)^2 \big\} \\ &= \min_{0 \leq j < i}\big\{ -2(s_i-L)s_j + (f_j+s_j^2) \big\} + (s_i-L)^2 \end{aligned} $$ 写成斜率优化的标准形式,b = kx + y 这里有:

  • $$k = -2(s_i-L)$$
  • $$x = s_j $$
  • $$y = f_j + x^2 $$

这里 $$x$$ 和 $$k$$ 均单调(因为 $$s_i$$ 单调),单调队列即可。

//}/* .................................................................................................................................. */

const int N = int(5e4) + 9;

LL f[N], s[N]; int q[N], cz, op;
int n, L;

#define k (-2*(s[i]-L))
#define x(i) (s[i])
#define y(i) (f[i]+sqr(x(i)))
#define eval(i) (k*x(i)+y(i))

LL det(LL x1, LL y1, LL x2, LL y2){
    return x1*y2 - x2*y1;
}

int dett(int p0, int p1, int p2){
    LL t = det(x(p1)-x(p0), y(p1)-y(p0), x(p2)-x(p0), y(p2)-y(p0));
    return t < 0 ? -1 : t > 0;
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    RD(n, L); REP_1(i, n) s[i] = s[i-1] + RD();
    REP_1(i, n) s[i] += i; ++L;

    cz = 0, op = 0; q[cz] = 0; REP_1(i, n){
        while (cz < op && eval(q[cz]) >= eval(q[cz+1])) ++cz;
        f[i] = eval(q[cz]) + sqr(s[i]-L);
        while (cz < op && dett(q[op-1], q[op], i) <= 0) --op;
        q[++op] = i;
    }

    OT(f[n]);
}