题目描述
http://www.lydsy.com/JudgeOnline/problem.php?id=3156
输入
第一行为一个整数N表示战线的总长度。
第二行N个整数，第i个整数表示在位置i放置守卫塔的花费Ai。
输出
共一个整数，表示最小的战线花费值。
样例输入
10
2 3 1 5 4 5 6 3 1 2
样例输出
18
题解
dp+斜率优化
设f[i]为第i个建检查站时前i个的最小代价。
那么就有f[i]=f[j]+∑(i-t) (j+1≤t≤i)
=f[j]+i*(i-j)-∑t (j+1≤t≤i)
=f[j]+i*(i-j)-(sum[i]-sum[j])
其中sum[i]为1~i的和（别问我为什么不用i*(i+1)/2，那玩意太慢）
整理一下就是f[j]+sum[j]=i*j+f[i]+sum[i]-i*i-a[i]。
这样就变为了y=kx+b的形式。
由于这里b中f[i]的系数是正的，所以要求的就是b的最大值。
维护一个下凸包即可。
需要注意的是q和i也要开long long，毕竟相乘的时候如果都是int就会爆，这里懒了直接全long long。
#include <cstdio>
#define y(i) (f[i] + sum[i])
long long f[1000010] , a[1000010] , sum[1000010] , q[1000010] , l , r;
int main()
{
long long n , i;
scanf("%lld" , &n);
for(i = 1 ; i <= n ; i ++ )
scanf("%lld" , &a[i]) , sum[i] = sum[i - 1] + i;
for(i = 1 ; i <= n ; i ++ )
{
while(l < r && y(q[l + 1]) - y(q[l]) < (q[l + 1] - q[l]) * i) l ++ ;
f[i] = y(q[l]) - i * q[l] - sum[i] + i * i + a[i];
while(l < r && (y(i) - y(q[r])) * (q[r] - q[r - 1]) < (i - q[r]) * (y(q[r]) - y(q[r - 1]))) r -- ;
q[++r] = i;
}
printf("%lld\n" , f[n]);
return 0;
}
原文：http://www.cnblogs.com/GXZlegend/p/6433394.html