【BZOJ3156】防御准备 斜率优化

【BZOJ3156】防御准备

Description

【BZOJ3156】防御准备 斜率优化

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

题解:一眼看出斜率优化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;
}
上一篇:B. Interesting drink


下一篇:ffmpeg中AVBuffer的实现分析