从 $n$ 开始倒序转移把距离预处理成到n的距离，然后把工厂编号倒转一下

方程 （编号倒转后的）

代码里 $num[i]$ 就是 $p_i$ $dis[i]$ 是 $x[i]$

然后前缀和优化 $Num[i]$ 前缀和 $num[i]$ ，$Nd[i]$ 前缀和 $num[i]*dis[i]$

优化后方程就是

最后枚举所有工厂，看看如果不在 $n$ （转编号之前的1号）建工厂的最优解是什么然后判断

然鹅 11pts

#include<bits/stdc++.h>
#define int long long
#define Maxn 1000001
#define X(i) dis[i]
#define Y(i) dp[i]-Nd[i]+Num[i]*dis[i]
using namespace std;
int dp[Maxn],dis_[Maxn],dis[Maxn],Num[Maxn],num[Maxn],Nd[Maxn],c[Maxn];
int deq[Maxn],h,t,ans;
int n;
signed main()
{
	cin>>n;
	for(int i=n;i>=1;i--)
		cin>>dis_[i]>>num[i]>>c[i],Num[i]=num[i];
	for(int i=1;i<=n;i++)
		dis[i]=dis_[1]-dis_[i],Num[i]+=Num[i-1],Nd[i]=num[i]*dis[i]+Nd[i-1];
	deq[1]=1,dp[1]=c[1];
	h=t=1;
	for(int i=2;i<=n;i++)
	{
		while(h<t&&Y(deq[h+1])-Y(deq[h])<(X(deq[h+1])-X(deq[h]))*Num[i-1])
			h++;
		dp[i]=Y(deq[h])+Nd[i-1]-dis[deq[h]]*Num[i-1]+c[i];
		while(h<t&&(Y(i)-Y(deq[t-1]))*(X(deq[t])-X(deq[t-1]))<(Y(deq[t])-Y(deq[t-1]))*(X(i)-X(deq[t-1])))
			t--;
		deq[++t]=i;
	}
	ans=Nd[n]-Nd[1]+dp[1];
	for(int i=2;i<=n-1;i++)
		ans=min(dp[i]+Nd[n]-Nd[i],ans);
	cout<<min(ans,dp[n]);
}
/*
3
0 5 20
4 7 30
11 5 100
*/