社区讨论
关于斜率优化蒟蒻有个问题
P3628[APIO2010] 特别行动队参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lodcwsgu
- 此快照首次捕获于
- 2023/10/31 04:32 2 年前
- 此快照最后确认于
- 2023/11/06 19:54 2 年前
之前一直A不了,看了题解跟题解对了后发现判断斜率时多了个=(下面代码加 号的地方),但如果关于 的某式,不是代表一样优秀吗?那我删去,留下;和,都留下为什么会对结果造成影响呀。
CPP#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;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...