【题解】BZOJ 3156 防御准备

Problem

给定一个长度为 $n$ 的序列,每个位置可以放木偶或者守卫塔

放置守卫塔费用为 $a_i$
放置木偶费用为右侧第一个守卫塔距离

求最小花费

Thought

观察发现可以将守卫塔的位置作为状态,两个守卫塔之间必然是木偶

设 $f[i]$ 表示第 $i$ 个位置放置守卫塔的最小费用,有转移:

$$ f[i]=\min\{f[j]+cost(j,i)\}+a[i] $$

其中 $cost(j,i)$ 为 $(j,i)$ 位置到 $i$ 的距离和,在这里也就是 $\frac{(i-j)(i-j-1)}{2}$

$$ f[i]=\min\{f[j]+\frac{i^2-i-2ij+j^2+j}{2}\}+a[i] $$

若 $j<k$ ,并且决策 $k$ 比决策 $j$ 优,则:

$$ f[j]+\frac{i^2-i-2ij+j^2+j}{2}>f[k]+\frac{i^2-i-2ik+k^2+k}{2}\\ f[j]+\frac{j^2+j}{2}-ij>f[k]+\frac{k^2+k}{2}-ik $$

发现相当于是求两个形似于 $kx+b$ 的式子在 $i$ 处的取值

考虑将其转化为平面上点的形式,相当于是过点 $(j,f[j]+\frac{j^2+j}{2}),(k,f[k]+\frac{k^2+k}{2})$ 的斜率为 $i$ 的直线的截距

由于需要取截距最小值,观察发现只需要维护一个上凸包,并且 $i$ 单调,用单调队列维护即可

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 1000010;
typedef long long ll;
int n, a[N];
ll f[N];
int q[N], tail, head;
double slope(ll x, ll y) {
    return (double)((f[y] + y * (y + 1) / 2) - (f[x] + x * (x + 1) / 2)) / (double) (y - x);
}
int main() {
    n = read();
    for(int i = 1; i <= n; ++ i)
        a[i] = read();
    head = 1; tail = 1;
    q[head] = 0;
    for(int i = 1; i <= n; ++ i) {
        while(head > tail && slope(q[tail], q[tail + 1]) <= i) q[tail ++] = 0;
        f[i] = f[q[tail]] + 1ll * (i - q[tail]) * (i - q[tail] - 1) / 2 + a[i];
        while(head > tail && slope(q[head - 1], q[head]) >= slope(q[head], i)) q[head --] = 0;
        q[++ head] = i;
    }
    printf("%lld\n", f[n]);
    return 0;
}
Comments

添加新评论