社区讨论

关于斜率优化蒟蒻有个问题

P3628[APIO2010] 特别行动队参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lodcwsgu
此快照首次捕获于
2023/10/31 04:32
2 年前
此快照最后确认于
2023/11/06 19:54
2 年前
查看原帖
之前一直A不了,看了题解跟题解对了后发现判断斜率时多了个=(下面代码加 * 号的地方),但如果(Y(j1)Y(j2))/(X(j1)X(j2))==(Y(j1)-Y(j2))/(X(j1)-X(j2))==关于 ii 的某式,不是代表j1,j2j1,j2一样优秀吗?那我删去j1j1,留下j2j2;和j1j1,j2j2都留下为什么会对结果造成影响呀。
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 条回复,欢迎继续交流。

正在加载回复...