自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 22:40:54，当前版本为作者最后更新于2024-09-14 15:05:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先把道路的终点也看做一个家庭，这个家庭的人数是 $0$，到达公路起点的距离就是 $L$。

设 $dp_{i,j}$ 为在第 $i$ 户家庭修建第 $j$ 个集会地点，前 $i$ 户的开销之和的最小值，最终答案就是 $dp_{n+1,4}$。可以在开始的时候直接选择将 $n$ 加上 $1$，最后输出 $dp_{n,4}$。

状态转移方程：$dp_{i,j}=\min\limits_{k=0}^{i-1}(dp_{k,j-1}+\sum\limits_{p=k+1}^{i}(t_p\times(d_i-d_p)))$，在这之前要先将 $dp$ 初始化为无穷大。

显然如果直接这样做会直接 T 飞，所以考虑优化。

一个显而易见的优化是使用前缀和，设 $st_i=\sum\limits_{p=1}^{i}t_p$，$std_i=\sum\limits_{p=1}^{i}(t_p\times d_p)$，那么原状态转移方程就能写为：$dp_{i,j}=\min\limits_{k=0}^{i-1}(dp_{k,j-1}+d_i\times(st_i-st_k)-(std_i-std_k))$，拆括号并整理得到 $dp_{i,j}=\min\limits_{k=0}^{i-1}(dp_{k,j-1}+std_k-d_i\times st_k+d_i\times st_i-std_i)$。

为什么要这么整理呢？因为不难发现在本题的情况下，决策单调性是显然的，将转移式改成 $y=kx+b$ 的形式，就可以用斜率优化 dp。

去除 $\min$ 并将转移式改写成 $dp_{k,j-1} + std_k = d_i\times st_k + std_i - d_i\times st_i + dp_{i,j}$，并令：

要让 $dp_{i,j}$ 最小，则要 $b$ 最小，单调队列维护下凸壳即可。

具体在 dp 的时候要先推一遍 $j=1$ 的情况。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
/*
dp[i][j] 在第 i 户家庭修建第 j 个集会地点，前 i 户的开销最小值
dp[i][j] = min[k=0,i-1](dp[k][j-1]+sum[p=k+1,i](t[p]*(d[i]-d[p])))
dp[i][j] = min[k=0,i-1](dp[k][j-1]+sum[p=k+1,i](t[p]*d[i])-sum[p=k+1,i](t[p]*d[p]))
dp[i][j] = min[k=0,i-1](dp[k][j-1] + sum[p=k+1,i]t[p]*d[i] - sum[p=k+1,i](t[p]*d[p]))
设 st[i] = sum[p=1,i](t[p]), std[i] = sum[p=1,i]t[p]*d[p]
dp[i][j] = min[k=0,i-1](dp[k][j-1] + (st[i]-st[k])*d[i] - (std[i]-std[k]))
dp[i][j] = min[k=0,i-1](dp[k][j-1] + st[i]*d[i] - st[k]*d[i] - std[i] + std[k]) 注：st[i]*d[i] 不等于 std[i]
dp[k][j-1] + st[i]*d[i] - st[k]*d[i] - std[i] + std[k] - dp[i][j] = 0
dp[k][j-1] = - st[i]*d[i] + st[k]*d[i] + std[i] - std[k] + dp[i][j]
dp[k][j-1] + std[k] = d[i]*st[k] + std[i] - st[i]*d[i] + dp[i][j]
y                   = k    x     + b
求最小维护下凸壳 
*/
int n,L,d[N],t[N],dp[N][5],st[N],st_d[N],q[N];
double K(int p1,int p2,int j){
	double xp1=st[p1];
	double xp2=st[p2];
	double yp1=dp[p1][j-1]+st_d[p1];
	double yp2=dp[p2][j-1]+st_d[p2];
	return (yp2-yp1)/((xp2-xp1==0)?1e-9:xp2-xp1);
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>L;
	for(int i=1;i<=n;i++)cin>>d[i]>>t[i];
	d[++n]=L;t[n]=0;
	for(int i=1;i<=n;i++)st[i]=st[i-1]+t[i],st_d[i]=st_d[i-1]+t[i]*d[i];
	//初始化 j=1 的情况
	for(int j=1;j<=1;j++){
		for(int i=1;i<=n;i++){
			dp[i][j]=dp[i-1][j]+(d[i]-d[i-1])*st[i-1];//将前面所有 st[i-1] 个人全部迁移 (d[i]-d[i-1]) 的长度 
		}
	} 
	for(int j=2;j<=4;j++){
		for(int i=0;i<=n;i++)q[i]=0;
		for(int i=0;i<=n;i++)dp[i][j]=(1ll<<60);
		int h=1,aqua=0;
		for(int i=1;i<=n;i++){
			while(h<aqua&&K(q[aqua-1],q[aqua],j)>=K(q[aqua-1],i-1,j))aqua--;
			q[++aqua]=i-1;
			while(h<aqua&&K(q[h],q[h+1],j)<=d[i])h++;
			int k=q[h];
			dp[i][j]=dp[k][j-1]+st[i]*d[i]-st[k]*d[i]-st_d[i]+st_d[k];
		}
	}
	cout<<dp[n][4];
	return 0;
}