【斜率优化dp】防御准备

动态规划DP

传送门：BZOJ3156

思路：用$f_i$表示第i个点建站时前i个的最小代价，dp即可，可以斜率优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
#define N 1200000
#define INF 0x3f3f3f3f
LL n,a[N],f[N],x[N],y[N],q[N];
LL getint(){
	char ch; LL sum=0;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
	return sum;
}
double K(int u,int v){return (double)(1.0*(y[u]-y[v]))/(x[u]-x[v]);}
int main(){
	n=getint();
	for (int i=1;i<=n;i++) a[i]=getint();
	
	memset(f,INF,sizeof f); f[0]=0; x[0]=0; y[0]=0;
	int tt=1,ww=1; q[1]=0;
	for (int i=1;i<=n;i++){
		while (tt<ww && K(q[tt],q[tt+1])<=i) tt++;
		int j=q[tt]; f[i]=-x[j]*i+y[j]+a[i]+(1LL*i*i-i)/2; x[i]=i; y[i]=f[i]+(1LL*i*i+i)/2;
		while (tt<ww && K(q[ww-1],q[ww])>=K(q[ww],i)) ww--; q[++ww]=i;
	}
	printf("%lld\n",f[n]);
	
	return 0;
}