题目描述

Description

Input

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

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

Output

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

Sample Input

10
2 3 1 5 4 5 6 3 1 2

Sample Output

18

HINT

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

题目分析

令f[i]为第i个点放塔 1~i战线花费最小值
列出方程：
f[i]=f[j]+∑(i-t) (j+1≤t≤i) +c[i]
=f[j]+i*(i-j)-∑t (j+1≤t≤i) +c[i]
=f[j]+i*(i-j)-(sum[i]-sum[j]) +c[i]
移项：f[j]+sum[j]=i*j+f[i]+sum[i]-i*i-c[i]
之后斜率优化即可

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
long long sum[2000000],f[2000000],c[2000000];
int n,l,r;
long long q[2000000];
long long yi(long long i) { return f[i]+sum[i]; }
int main()
{
    scanf("%d",&&n);
    for(int i=1;i<=n;i++) scanf("%lld",&&c[i]);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+i;
    for(int i=1;i<=n;i++)
    {
        while(l<r&&&&yi(q[l+1])-yi(q[l])<i*(q[l+1]-q[l])) l++;
        f[i]=f[q[l]]+i*(i-q[l])-sum[i]+sum[q[l]]+c[i];
        while(l<r&&&&(yi(i)-yi(q[r]))*(q[r]-q[r-1])<(yi(q[r])-yi(q[r-1]))*(i-q[r])) r--;
        q[++r]=i;
    }
    printf("%lld",f[n]);
}
/*f[i]=f[j]+i*(i-j)-sum[i]+sum[j]+c[i];
f[j]+sum[j]=i*j+sum[i]-i*i+f[i]-c[i];*/