关于斜率优化蒟蒻有个问题
查看原帖
关于斜率优化蒟蒻有个问题
233957
190040257a楼主2020/8/19 20:11

之前一直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都留下为什么会对结果造成影响呀。

#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;
}
2020/8/19 20:11
加载中...