bzoj3156 防御准备

3156: 防御准备

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 2361 Solved: 997
[Submit][Status][Discuss]

Description

Input

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

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

Output

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

Sample Input

10
2 3 1 5 4 5 6 3 1 2

Sample Output

HINT

1<=N<=10^6,1<=Ai<=10^9

Source

Katharon+#1

分析：为了方便处理，将a序列翻转过来，那么题目就变成了从左往右处理.

　　　首先很容易能想到这道题要用到斜率优化，why? 想象一下，枚举一个点i,如果当前点y要放木偶，总得在前面找一个位置放守望塔吧，那么这就是O(n^2)的了，朴素dp的复杂度都是如此，需要对此优化，如何优化，那就是斜率dp咯.

　　　我一开始想的状态是f[i][0/1]表示前i个位置中，第i个位置放守望塔还是木偶的最小花费值. 可以转移，但这不是斜率优化的那种式子啊......

　　　斜率优化要求一维的状态，那我的后面一个状态能不能去掉呢？如果令f[i]表示前i个位置中，第i个位置放守望塔的最小化费值，可以枚举前面一个放守望塔的位置j,在j+1 到 i-1之间都放木偶，这个答案是能够计算出来的.

　　　f(i) = min{f(j) + sum[i - 1] - sum[j] - (i - 1 - j) * d[j] + a[i]}. d[i]表示i到1的距离,sum[i]表示d数组的前缀和，a[i]表示建守望塔的花费.

　　　然后就是斜率优化的常规套路了. 注意这里要求min,求的是上凸壳，别弄反了！

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll maxn = 1000010;
ll n,a[maxn],l,r,f[maxn],q[maxn],sum[maxn],d[maxn],ans;

ll K(ll i)
{
    return -d[i];
}

ll B(ll i)
{
    return i * d[i] + f[i] - sum[i];
}

ll Y(ll i,ll j)
{
    return K(i) * (j - 1) + B(i);
}

bool cmp(ll y1,ll y2,ll y3)
{
    ll temp1 = (K(y1) - K(y3)) * (B(y2) - B(y1));
    ll temp2 = (K(y1) - K(y2)) * (B(y3) - B(y1));
    return temp1 >= temp2;
}

int main()
{
    scanf("%lld",&n);
    for (ll i = 1; i <= n; i++)
        scanf("%lld",&a[i]);
    for (int i = 1, j = n; i <= j; i++,j--)
        swap(a[i],a[j]);
    d[1] = 0;
    for (ll i = 2; i <= n; i++)
        d[i] = d[i - 1] + 1;
    for (ll i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + d[i];
    f[1] = a[1];
    q[r] = 1;
    for (ll i = 2; i <= n; i++)
    {
        while (l < r && Y(q[l],i) >= Y(q[l + 1],i))
            l++;
        f[i] = Y(q[l],i) + sum[i - 1] + a[i];
        while (l < r && cmp(i,q[r - 1],q[r]))
            r--;
        q[++r] = i;
    }
    ans = f[n];
    for (ll i = 1; i < n; i++)
        ans = min(ans,f[i] + sum[n] - sum[i] - d[i] * (n - i));
    printf("%lld
",ans);

    return 0;
}