题意
https://cn.vjudge.net/problem/HDU-3507
分析
斜率优化的模板题
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 6 using namespace std; 7 typedef long long LL; 8 const int maxn=500000+10; 9 int n,m; 10 int c[maxn],sum[maxn],f[maxn],q[maxn]; 11 int head,tail; 12 int Y(int j){ 13 return f[j]+sum[j]*sum[j]; 14 } 15 int X(int j){ 16 return sum[j]; 17 } 18 19 double grand(int i,int j){ 20 return (Y(i)-Y(j))/(X(i)-X(j)); 21 } 22 23 int main(){ 24 while(scanf("%d%d",&n,&m)!=EOF){ 25 for(int i=1;i<=n;i++){ 26 scanf("%d",&c[i]); 27 sum[i]=sum[i-1]+c[i]; 28 } 29 head=tail=0; 30 q[tail++]=0; 31 for(int i=1;i<=n;i++){ 32 while(head+1<tail&&((Y(q[head+1])-Y(q[head]))<=2*sum[i]*(X(q[head+1])-X(q[head]))))head++; 33 f[i]=f[q[head]]+(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]])+m; 34 // printf("%d %d %d ",i,q[head],f[i]); 35 // printf("%d %d ",head,tail); 36 while(head+1<tail&&((Y(q[tail-1])-Y(q[tail-2]))*(X(i)-X(q[tail-1]))>=(X(q[tail-1])-X(q[tail-2]))*(Y(i)-Y(q[tail-1]))))tail--; 37 q[tail++]=i; 38 } 39 40 printf("%d ",f[n]); 41 } 42 return 0; 43 }