求助模板斜率优化SOS

预处理时间的前缀和为

pret[i]

(包括

i

),费用系数的后缀和

suf[i]

(不包括

i

),转移方程为

f[i]=\min\{f[j]+(s+pret_i-pret_j)*suf[j]\}

f[i]=f[j]+(s-pret_j)*suf[j]+pret_i*suf[j]

-pret_i*suf_j+f[i]=f[j]+(s-pret_j)*suf[j]

把

-pret_i

看作斜率,把

suf_j

看作自变量

x

,等式右边看作因变量

y

我们要找的就是最小的截距。

由于斜率是负的且单调递减,到这里我已经觉得没法写了

然后维护上凸壳

ac

虽然上凸壳也满足斜率递减,但是

-pret_i

是负数啊,这样找切线不是求的最大截距么

这样为什么是对的...

如图红色的线斜率为

-pret_i

,应该是在切点处截距取到最小值,但是切点并不在上凸壳??

CPP

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int n,s,suf[maxn],pret[maxn],xi[maxn],f[maxn];
int head = 1, tail = 0, q[maxn];
int x(int i){ return suf[i]; }
int y(int i){ return f[i]+(s-pret[i])*suf[i]; }
double slope(int i,int j)
{
	return ( 1.0*y(i)-y(j) )/( 1.0*x(i)-x(j) );
}
int main()
{
	cin >> n >> s;
	for(int i=1;i<=n;i++)	cin >> pret[i] >> xi[i];
	for(int i=n;i>=0;i--)	suf[i] = suf[i+1]+xi[i+1];
	for(int i=1;i<=n;i++)	pret[i] += pret[i-1];
	q[++tail] = 0;
	for(int i=1;i<=n;i++)
	{
		while( head+1<=tail && slope(q[head],q[head+1])>( -pret[i] ) )	head++;
		int las = q[head];
		f[i] = f[las]+( s-pret[las] )*suf[las]+pret[i]*suf[las];
		while( tail-1>=head && slope(q[tail-1],q[tail])<slope(q[tail],i) )	tail--;
		q[++tail] = i;
	}
	cout << f[n];
}

是我哪里搞错了吗?....

求助模板斜率优化SOS

讨论操作

回复

相关推荐

求助模板斜率优化SOS