@[limaopipi2022](/user/160839) 你循环条件写错了啊
by Seauy @ 2020-07-20 23:01:47
我的过了,循环条件自己比对一下
```cpp
/*
f[i]=max(f[j]+aX^2+bX+c)
X=sum(j+1,i)
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e6;
int n;
ll a,b,c,p[MAXN+5];
ll f[MAXN+5];
deque<int> Q;
ll Sum(int L,int R)
{
if(L>R) return 0;
return p[R]-p[L-1];
}
ll X_(ll X) {return a*X*X+b*X+c;}
ll dy(int k,int j) {return a*(p[j]+p[k])*(p[j]-p[k])+f[j]-f[k];}
ll dx(int k,int j) {return p[j]-p[k];}
int main()
{
scanf("%d",&n);
scanf("%lld %lld %lld",&a,&b,&c);
for(int i=1,x;i<=n;i++)
{
scanf("%d",&x);
p[i]=p[i-1]+x;
}
Q.push_back(0);
for(int i=1;i<=n;i++)
{
for(int k,j;Q.size()>1;Q.pop_front())
{
k=Q[0],j=Q[1];
if(dy(k,j)<=(2*a*p[i]+b)*dx(k,j)) break;
}
if(i>1) f[i]=f[Q.front()]+X_(Sum(Q.front()+1,i));
else f[1]=X_(Sum(1,1));
for(int k,j;Q.size()>1;Q.pop_back())
{
k=Q[Q.size()-2],j=Q[Q.size()-1];
if(dy(k,j)*dx(k,i)>=dy(k,i)*dx(k,j)) break;
}
Q.push_back(i);
}
printf("%lld\n",f[n]);
return 0;
}
```
by Seauy @ 2020-07-20 23:03:15
@[QuantumCheshireCat](/user/54591) 哪儿的条件?(
by Prean @ 2020-07-20 23:31:33
@[limaopipi2022](/user/160839) 弹队头和队尾的条件
by Seauy @ 2020-07-21 08:29:12
@[QuantumCheshireCat](/user/54591) 队内至少一个元素?
那我是不是每次都应该判断一下0/yiw
by Prean @ 2020-07-21 08:30:51
@[limaopipi2022](/user/160839) 另外一个条件……
同样的条件,我的是满足就退出,你的是满足就继续
by Seauy @ 2020-07-21 09:56:25
@[QuantumCheshireCat](/user/54591) A了,谢谢
by Prean @ 2020-07-21 09:58:35