.jpg)
第一行为一个整数N表示战线的总长度。
第二行N个整数，第i个整数表示在位置i放置守卫塔的花费Ai。
共一个整数，表示最小的战线花费值。
1<=N<=10^6,1<=Ai<=10^9
斜率优化DP
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 1000005
using namespace std;
int n,l,r,a[maxn];
ll q[maxn],f[maxn];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline double getk(ll x,ll y)
{
return (double)(f[x]+(x*x+x)/2-f[y]-(y*y+y)/2)/(double)(x-y);
}
int main()
{
n=read();
F(i,1,n) a[i]=read();
l=r=1;q[1]=0;
for(ll i=1;i<=n;i++)
{
while (l<r&&getk(q[l],q[l+1])<i) l++;
f[i]=f[q[l]]+(q[l]*q[l]+q[l])/2-q[l]*i+a[i]+(i*i-i)/2;
while (l<r&&getk(q[r-1],q[r])>getk(q[r],i)) r--;
q[++r]=i;
}
printf("%lld\n",f[n]);
return 0;
}
原文：http://blog.csdn.net/aarongzk/article/details/51440720