预处理时间的前缀和为$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$,应该是在切点处截距取到最小值,但是切点并不在上凸壳??

#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];
}

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