http://www.lydsy.com/JudgeOnline/problem.php?id=1911

又是一個顯然的dp……好吧我懶得講了。

s[i]是戰斗力前綴和。

我們仍然設k<j<i，化簡一下得到f[j]-2*a*s[i]s[j]+a*s[j]^2-b*s[j]>f[k]-2*a*s[i]s[k]+a*s[k]^2-b*s[k]

于是得到：

0.5*(f[j]+a*s[j]*s[j]-b*s[j]-f[k]-a*s[k]*s[k]+b*s[k])/(a*(s[j]-s[k]))<s[i]

顯然可以斜率優化了。

（為什么變號，emmmmmm……a<0）

至于剩下的套路部分就請看土地購買這道題的解法吧。

#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; const int N=1000010; const ll INF=1e18; inline int read(){int X=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9')X=(X<<1)+(X<<3)+ch-'0',ch=getchar();return X*w; } int n,l,r; ll a,b,c; ll f[N],q[N],s[N]; inline double suan(int k,int j){return 0.5*(f[j]+a*s[j]*s[j]-b*s[j]-f[k]-a*s[k]*s[k]+b*s[k])/(a*(s[j]-s[k])); } int main(){n=read(),a=read(),b=read(),c=read();for(int i=1;i<=n;i++)s[i]=s[i-1]+read();for(int i=1;i<=n;i++){while(l<r&&suan(q[l],q[l+1])<(double)s[i])l++;ll k=s[i]-s[q[l]];f[i]=f[q[l]]+a*k*k+b*k+c;while(l<r&&suan(q[r],i)<suan(q[r-1],q[r]))r--;q[++r]=i;}printf("%lld\n",f[n]);return 0; }

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+歡迎訪問我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

轉載于:https://www.cnblogs.com/luyouqi233/p/8410756.html

總結

以上是生活随笔為你收集整理的BZOJ1911：[Apio2010]特别行动队——题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。