之前一直A不了,看了题解跟题解对了后发现判断斜率时多了个=(下面代码加 ∗ 号的地方),但如果(Y(j1)−Y(j2))/(X(j1)−X(j2))==关于 i 的某式,不是代表j1,j2一样优秀吗?那我删去j1,留下j2;和j1,j2都留下为什么会对结果造成影响呀。
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int N;
int a,b,c;
long long f[1000902];
long long sum[1000902];
int head=1;
int tail=0;
int que[1000010];
int read()
{
int w=1;
int s=0;
char ch;
ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
long double sumk(int j1,int j2)
{
return ((f[j1]-f[j2])+(a*sum[j1]*sum[j1]-b*sum[j1]-a*sum[j2]*sum[j2]+b*sum[j2]))/(sum[j1]-sum[j2])*1.0;
}
int main()
{
N=read();
a=read();
b=read();
c=read();
for(int i=1;i<=N;i++)
{
sum[i]=read();
sum[i]+=sum[i-1];
}
que[++tail]=0;
for(int i=1;i<=N;i++)
{
while(head<tail&&sumk(que[head],que[head+1])>(2*a*sum[i]))//*****之前加了个=
head++;
int j=que[head];
f[i]=f[j]+a*(sum[i]-sum[j])*(sum[i]-sum[j])+b*(sum[i]-sum[j])+c;
while(head<tail&&sumk(que[tail-1],que[tail])<=sumk(que[tail],i))tail--;
que[++tail]=i;
}
cout<<f[N];
return 0;
}