传送门
斜率优化dp经典题。
题目中说的很清楚，设f[i]表示前i个数分配出的最大值。
那么有：
f[i]=max(f[j]+A∗(sum[i]−sum[j])2+B∗(sum[i]−sum[j])+C)" role="presentation" style="position: relative;">f[i]=max(f[j]+A∗(sum[i]−sum[j])2+B∗(sum[i]−sum[j])+C)f[i]=max(f[j]+A∗(sum[i]−sum[j])2+B∗(sum[i]−sum[j])+C)
=>
f[i]=max(f[j]+A∗sum[j]2−2∗A∗sum[i]∗sum[j]−B∗sum[j])+A∗sum[i]2+B∗sum[i]+C" role="presentation" style="position: relative;">f[i]=max(f[j]+A∗sum[j]2−2∗A∗sum[i]∗sum[j]−B∗sum[j])+A∗sum[i]2+B∗sum[i]+Cf[i]=max(f[j]+A∗sum[j]2−2∗A∗sum[i]∗sum[j]−B∗sum[j])+A∗sum[i]2+B∗sum[i]+C
同样是比较两个决策k1,k2如果k1优于k2，那么：
f[k1]+A∗sum[k1]2−2∗A∗sum[i]∗sum[k1]−B∗sum[k1]" role="presentation" style="position: relative;">f[k1]+A∗sum[k1]2−2∗A∗sum[i]∗sum[k1]−B∗sum[k1]f[k1]+A∗sum[k1]2−2∗A∗sum[i]∗sum[k1]−B∗sum[k1]
>
f[k2]+A∗sum[k2]2−2∗A∗sum[i]∗sum[k2]−B∗sum[k2])" role="presentation" style="position: relative;">f[k2]+A∗sum[k2]2−2∗A∗sum[i]∗sum[k2]−B∗sum[k2])f[k2]+A∗sum[k2]2−2∗A∗sum[i]∗sum[k2]−B∗sum[k2])
为了让每次查询的斜率单调递增。
我们需要巧妙地移项：
令t[k]=f[k]+A∗sum[k]2−B∗sum[k]" role="presentation" style="position: relative;">t[k]=f[k]+A∗sum[k]2−B∗sum[k]t[k]=f[k]+A∗sum[k]2−B∗sum[k]
=>(t[k1]−t[k2])>2∗A∗sum[i]∗(sum[k1]−sum[k2])" role="presentation" style="position: relative;">(t[k1]−t[k2])>2∗A∗sum[i]∗(sum[k1]−sum[k2])(t[k1]−t[k2])>2∗A∗sum[i]∗(sum[k1]−sum[k2])
=>slope(k1,k2)/A<2∗sum[i]" role="presentation" style="position: relative;">slope(k1,k2)/A<2∗sum[i]slope(k1,k2)/A<2∗sum[i]
搞定了。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
inline ll read(){
ll ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*w;
}
int n,q[N],hd,tl;
ll A,B,C,sum[N],f[N];
inline double slope(int i,int j){return 1.0*(sum[i]+sum[j])+(1.0*(f[i]-f[j])/(sum[i]-sum[j])-B)*1.0/A;}
int main(){
n=read(),A=read(),B=read(),C=read(),hd=tl=1;
for(int i=1;i<=n;++i)sum[i]=sum[i-1]+read();
for(int i=1;i<=n;++i){
while(hd<tl&&slope(q[hd+1],q[hd])<2*sum[i])++hd;
int j=q[hd];
f[i]=f[j]+A*(sum[i]-sum[j])*(sum[i]-sum[j])+B*(sum[i]-sum[j])+C;
while(hd<tl&&slope(i,q[tl])<slope(q[tl],q[tl-1]))--tl;
q[++tl]=i;
}
cout<<f[n];
return 0;
}