正解 \(O(n)\) 的做法（\(100pts\)）

思路分析

还是把状态转移方程搬过来：

去掉 \(min\)，再展开整理一下：

把与 \(j\) 有关和与 \(j\) 无关的分开：

移项：

可以发现括号里面的部分都和 \(i\) 有关、和 \(j\) 无关，而括号外面的部分则和 \(j\) 有关。
我们设 \(Y=dp_j+sumxp_j\)，\(X=sump_j\)，\(K=-x_i\)，\(B=(dp_i+sumxp_i-c_i-x_i\cdot sump_i)\)，那么上面的式子就变成了：

显然，我们要求 \(dp_i\) 最小，就是求 \(B\) 最小，此时：

（下面就是斜率优化 DP 这类型题非常套路的地方）：

对于两个决策点 \(a，如果 \(b\) 比 \(a\) 更优，则：

整理得：

即：

由于 \(x_i\) 随 \(i\) 单调递增，可以用单调队列维护一个下凸壳。

维护凸壳时，对于三个点 \(a,b,c\)，若 \(b\) 不在凸壳上，则满足：

此时弹出 \(b\)。

查询最优决策时，若队首的下一个点比队首更优，则弹出队首。

细节方面的处理

1. \(p_i\) 可能为 \(0\)

当 \(p_i=0\) 时，\(sump[i]=sump[i-1]\)，即 \(X\) 坐标可能相同。此时凸壳中会出现竖直方向上的多个点。

对于相同的 \(X\)，我们只需要保留 \(Y\) 最小的那个点（即费用更小的点）。

在插入新点 \(i-1\) 之前，如果发现它与队尾点的 \(X\) 相同，就比较 \(Y\)：

• 若新点 \(Y\) 更小，则删除队尾旧点；
• 若新点 \(Y\) 更大，则直接不插入新点。

2. 最终答案不一定在 \(n\)

这里就和上面 \(O(n^3)\)、\(O(n^2)\) 的解法的注意点一样了，忘了的可以点击跳转。

3. 乘法溢出

凸壳判断和斜率比较中的乘法要用 __int128。

代码

#include
using namespace std;
typedef long long ll;
uint8_t buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
ll rd(){
	ll x=0,f=1,ch=gc();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
            f=-1;
        }
        ch=gc();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch-'0');
		ch=gc();
	}
	return x*f;
}
void write(ll x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
}
const ll maxn=1e6+5;
ll n,x[maxn],p[maxn],C[maxn],sump[maxn],sumxp[maxn],l=1,r,q[maxn],dp[maxn],pos,ans;
bool flag;
ll gy(ll a){
	return dp[a]+sumxp[a];
}
ll gx(ll a){
	return sump[a];
}
bool check1(ll a,ll b,ll c){
	return (__int128)(gy(b)-gy(a))*(gx(c)-gx(a))>=(__int128)(gy(c)-gy(a))*(gx(b)-gx(a));
}
bool check2(ll a,ll b,ll c){
	return (__int128)gy(b)-gy(a)<=(__int128)x[c]*(gx(b)-gx(a));
}
int main(){
	n=rd();
	for(ll i=1;i<=n;i++){
		x[i]=rd();
		p[i]=rd();
		C[i]=rd();
		sump[i]=sump[i-1]+p[i];
		sumxp[i]=sumxp[i-1]+x[i]*p[i];
	}
	for(ll i=1;i<=n;i++){
        flag=true;
        if(l<=r&&gx(q[r])==gx(i-1)){
            if(gy(q[r])<=gy(i-1)){
                flag=false;
            }else{
                r--;
            }
        }
        if(flag){
            while(l=1;i--){
        if(p[i]>0){
            pos=i;
			ans=dp[pos];
            break;
        }
    }
    if(pos==0){
        putchar('0');
    }else{
       for(ll i=pos+1;i<=n;i++){
            if(dp[i]