【hdu3507】Print Article 【斜率优化dp】

时间:2021-05-20 17:53:43

题意

https://cn.vjudge.net/problem/HDU-3507

分析

斜率优化的模板题

 #include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std;
typedef long long LL;
const int maxn=+;
int n,m;
int c[maxn],sum[maxn],f[maxn],q[maxn];
int head,tail;
int Y(int j){
return f[j]+sum[j]*sum[j];
}
int X(int j){
return sum[j];
} double grand(int i,int j){
return (Y(i)-Y(j))/(X(i)-X(j));
} int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=;i<=n;i++){
scanf("%d",&c[i]);
sum[i]=sum[i-]+c[i];
}
head=tail=;
q[tail++]=;
for(int i=;i<=n;i++){
while(head+<tail&&((Y(q[head+])-Y(q[head]))<=*sum[i]*(X(q[head+])-X(q[head]))))head++;
f[i]=f[q[head]]+(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]])+m;
// printf("%d %d %d\n",i,q[head],f[i]);
// printf("%d %d\n",head,tail);
while(head+<tail&&((Y(q[tail-])-Y(q[tail-]))*(X(i)-X(q[tail-]))>=(X(q[tail-])-X(q[tail-]))*(Y(i)-Y(q[tail-]))))tail--;
q[tail++]=i;
} printf("%d\n",f[n]);
}
return ;
}