队列里至少要有两个元素吧,不然怎么算斜率啊(
就是把`L<=R`改成`L<R`
然后这是求最大值,维护的是单调上升的队列
```while(L<=R&&slope(q[L],q[L+1])>=2.0*a*sum[i])++L;```
```while(L<=R&&slope(q[R-1],q[R])<=slope(q[R],i))--R;```
然后您那个slope还有问题
by IntrepidStrayer @ 2020-07-20 06:56:09
@[fhh_orz](/user/214437) 上凸壳。。。。。
by Prean @ 2020-07-20 07:02:45
阿布,是单调下降
by IntrepidStrayer @ 2020-07-20 07:03:13
啊呸我个sb
by Prean @ 2020-07-20 07:04:56
@[fhh_orz](/user/214437) 好的现在每次检查队列队列里面只有两个元素
by Prean @ 2020-07-20 07:06:57
@[limaopipi2022](/user/160839) slope(a,b)和外面的ab重名了
by IntrepidStrayer @ 2020-07-20 07:11:39
@[fhh_orz](/user/214437) 草
现在dp[n]输出5(
by Prean @ 2020-07-20 07:13:16
建议将斜率式比较写成乘法,避免精度问题
by Acfboy @ 2020-07-20 07:25:14
@[limaopipi2022](/user/160839)
初始化L=R=1
然后斜率式有点问题~~重新推一遍吧~~
by Hauynite @ 2020-07-20 07:29:11
@[打表王子](/user/328855) 重写后代码如下:
```cpp
#include<cstdio>
#include<cctype>
const int M=1e6+5;
typedef long long ll;
ll a,b,c,sum[M],dp[M];
int n,L=1,R,q[M];
inline double slope(int x,int y){
return 1.0*(dp[y]-dp[x]+b*(sum[x]-sum[y]))/(sum[y]-sum[x])+a*(sum[y]+sum[x]);
}
inline ll read(){
ll n=0;char s;bool f=true;
while(!isdigit(s=getchar()))if(s==45)f=false;
while(n=n*10+(s^48),isdigit(s=getchar()));
return f?n:-n;
}
inline void print(){
for(int i=L;i<=R;++i)printf("%d ",q[i]);
printf("\n");
}
signed main(){
int i,j,x;
n=read();a=read();b=read();c=read();
for(i=1;i<=n;++i){
sum[i]=read()+sum[i-1];
// print();
while(L<=R&&slope(q[L],q[L+1])>=2.0*a*sum[i])++L;
j=q[L];x=(sum[i]-sum[j]);
dp[i]=dp[j]+a*x*x+b*x+c;
// print();
while(L<=R&&slope(q[R-1],q[R])<=slope(q[R],i))--R;
q[++R]=i;
// print();
// printf("%d %lld|\n",j,dp[i]);
}
printf("%lld",dp[n]);
}
```
~~斜率式的问题其实是第二个比较的地方都会减去b,就去掉了~~
还有,我的队列马蜂是左开右开。。。
by Prean @ 2020-07-20 07:30:43