【BZOJ3156】防御准备
Description
Input
第一行为一个整数N表示战线的总长度。
第二行N个整数，第i个整数表示在位置i放置守卫塔的花费Ai。
Output
共一个整数，表示最小的战线花费值。
Sample Input
10
2 3 1 5 4 5 6 3 1 2
2 3 1 5 4 5 6 3 1 2
Sample Output
18
HINT
1<=N<=10^6,1<=Ai<=10^9
题解：一眼看出斜率优化DP，先列出方程再说
令f[i]表示在i处放置守卫塔，且i左面的格子都被保护时的最小花费。
$f[i]=min(f[j]+\frac {(i-j)(i-j-1)} {2}+a[i]) (0\le j < i)$
整理一下，发现求的是下凸包，且点的坐标单调不减
题目图片太大导致不能再加图片了好气~
#include <cstdio>
#include <iostream>
#include <cstring>
#define y(_) (f[_]+_*(_+1)/2)
using namespace std;
typedef long long ll;
const int maxn=1000010;
int n;
ll q[maxn],h,t;
ll a[maxn],f[maxn];
int main()
{
scanf("%d",&n);
ll i;
for(i=1;i<=n;i++) scanf("%lld",&a[i]);
h=t=1;
for(i=1;i<=n;i++)
{
while(h<t&&(y(q[h+1])-y(q[h]))<=i*(q[h+1]-q[h])) h++;
f[i]=f[q[h]]+(i-q[h])*(i-q[h]-1)/2+a[i];
while(h<t&&(y(q[t])-y(q[t-1]))*(i-q[t])>=(y(i)-y(q[t]))*(q[t]-q[t-1])) t--;
q[++t]=i;
}
printf("%lld",f[n]);
return 0;
}