[BZOJ3156] 防御准备

2014-12-01
竞赛题解 / 动态规划
BZOJ

描述 Description

在美丽富饶的 Katharon 国中生活着一群快乐的小木偶。他们衣食无忧，自给自足。然而在某一天，来自外星的 X 国要对 Katharon 国发起攻击，国家安危迫在眉睫，下面请你来做战前的防御准备工作。

我们定义战线为一条长度为 n 的序列，在这条战线上共设有 n 个检查点， 从左到右依次标号为 1 到 n 。一个战线为合法战线当且仅当任意一个检查点可以通过安全检查。对于第 i 个检查点可以通过安全检查的方式有两种，第一种是放置一个守卫塔，这将花费 ai 的费用。第二种方式是放置一个木偶，放置木偶的花费等于这个检查点右侧的第一个守卫塔到它的距离。举例来说，若检查点 i 放置一个木偶，检查点 i 右侧的第一个守卫塔位置为 j(i ## 输入格式 InputFormat

第一行为一个整数 N 表示战线的总长度。

第二行 N 个整数，第 i 个整数表示在位置 i 放置守卫塔的花费 Ai。

输出格式 OutputFormat

共一个整数，表示最小的战线花费值。

样例输入 SampleInput

10
2 3 1 5 4 5 6 3 1 2

样例输出 SampleOutput

18

BZOJ 3156

斜率优化 DP。

原始方程： \[ f[i]=Min\{f[j]+\sum_{k=j+1}^{i}(i-k)\}+a[i] \]

化简得： \[ f[i]=Min\{f[j]+\frac{(i-j-1)*(i-j)}{2}\}+a[i] \]

设 \(k<j<i\) 且对于 \(i\) 而言 \(f[j]\) 优于 \(f[k]\)，则 \[ f[j]+\frac{(i-j-1)*(i-j)}{2}<f[k]+\frac{(i-k-1)*(i-k)}{2} \]

整理得： \[ \frac{(2*f[j]+j^2+j)-(2*f[k]+k^2+k)}{j-k}<2*i \]

于是用斜率优化来搞就好了。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
const ll maxn=1000005;
ll i,j,t,n,m,l,r,k,z,y,x;
ll a[maxn],f[maxn],q[maxn];
ll head,tail;
inline ll fracup(ll x,ll y)
{
    return (2*f[x]+x*x+x)-(2*f[y]+y*y+y);
}
inline ll fracdown(ll x,ll y)
{
    return x-y;
}
int main()
{
    scanf("%lld",&n);
    for (i=1;i<=n;i++) scanf("%lld",&a[i]);
    q[head=tail=0]=0;
    for (i=1;i<=n;i++)
    {
        while (tail>head && fracup(q[head+1],q[head])<2*i*fracdown(q[head+1],q[head])) head++;
        t=q[head];
        f[i]=f[t]+(i-t-1)*(i-t)/2+a[i];
        while (tail>head && fracup(q[tail],q[tail-1])*fracdown(i,q[tail])>fracup(i,q[tail])*fracdown(q[tail],q[tail-1])) tail--;
        q[++tail]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}