思路

首先考慮暴力DP，我們預處理出從第 \(1\) 個點到第 \(n\) 個點木材重量、運輸距離與運輸費用的前綴和，枚舉兩個鋸木廠的位置，設其分別在 \(i\) 點和 \(j\) 點。

易得狀態轉移方程為 $$ans=\min{f[j] \times (dis[j]-dis[i])+f[i] \times dis[i]-f[i] \times dis[n+1]+g[n+1]\ }$$ 其中 \(f[i]\) 表示木材重量，\(dis[i]\) 表示距離，\(g[i]\) 表示費用，時間復雜度 \(O(n^2)\)。

在P4360中，我們可以使用暴力DP水過該題，然而，加強數據后，明顯TLE，考慮優化。

觀察式子，我們分為只和 \(j\) 有關的，和 \(i\) 與 \(j\) 都有關的，只和 \(i\) 有關的三部分，可將其變形為 $$f[j] \times dis[j]=f[j] \times dis[i]-f[i] \times dis[i]+f[i] \times dis[n+1]+g[n+1]+ans$$ 對于該式子，可以進行斜率優化，我們想要使 \(-f[i] \times dis[i]+f[i] \times dis[n+1]+g[n+1]+ans\) 最小，也就是令一次函數的截距最小，下凸包維護各點，用斜率 \(dis[i]\) 查找即可，因為 \(dis[i]\) 與 \(f[i]\) 均遞增，可用單調隊列實現，復雜度 \(O(n)\) 十分優秀。

Code

#include<bits/stdc++.h>
#define ll long long
#define lb long double
using namespace std;
const int M=1e5+10;
int n,l;
ll w[M],d[M];
ll f[M],g[M],dis[M];
ll dp[M];
lb slope(int x,int y)
{
	return (lb)((lb)f[y]*dis[y]-(lb)f[x]*dis[x])/(lb)((lb)f[y]-(lb)f[x]);
}
int h=1,t=0,q[M];
int main()
{
	//memset(dp,0x7f,sizeof(dp));
	ll ans=1e18+5;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&w[i],&d[i]);
		f[i]=f[i-1]+w[i];
	}
	for(int i=2;i<=n+1;i++)
	{
		g[i]=g[i-1]+f[i-1]*d[i-1];
		dis[i]=dis[i-1]+d[i-1];
	}
	int j=1;
	q[++t]=1;
	for(int i=2;i<=n;i++)
	{
		while(h<t&&slope(q[h],q[h+1])<=dis[i]) h++;
		ans=min(ans,f[q[h]]*(dis[q[h]]-dis[i])+f[i]*dis[i]-f[i]*dis[n+1]+g[n+1]);
		while(h<t&&slope(q[t-1],q[t])>=slope(q[t],i)) t--;
		q[++t]=i;
		//ans=min(ans,f[j]*(dis[j]-dis[i])+f[i]*dis[i]-f[i]*dis[n+1]+g[n+1]);
	}
	printf("%lld\n",ans);
	return 0;
}
/* 
f[j]*dis[j] = f[j]*dis[i]  +  /-f[i]*dis[i]+f[i]*dis[n+1]+g[n+1]+ans/
  y					xk				常數b盡量小 
*/