自动搬运

查看原文

来自洛谷，原作者为

	lam_dyr 少年曾许凌云志，誓做天下第一流

搬运于2025-08-24 23:04:21，当前版本为作者最后更新于2025-08-20 07:58:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

被黄题硬控两天半（虽然在集训吧）。不过是道好题。

讲一下做这题的心路历程，看到有很多部分分决定先思考子任务 $2$ 和 $4$。结果 inf 年后发现无解都没判对 / gg。看了一眼题解发现全都是神秘的贪心结论，于是继续大力画图后推了 dp 式子最终 AC。和题解区做法暂时没有重复所以来写一篇。

Solve

题意很明确就不过多赘述了。

这里我们首先注意到要覆盖整段草坪，任意两台机器人之间的部分不能留空 —— 它们合力一定要把中间的“缝隙” 切掉。

令 $dp_{i,j}$ 表示已经处理了前 $i$ 台机器人的方向，且第 $i$ 台最终方向为 $j$（$0$ 表示向左，$1$ 表示向右）时所需的最小代价。最终答案就是 $\min(dp_{n,0},dp_{n,1})$。

考虑如何转移。假设我们已经算出了 $dp_{i-1,0}$ 和 $dp_{i-1,1}$，要推 $dp_{i,0}$ 和 $dp_{i,1}$。关键在于 $\Delta=x_i-x_{i-1}$ 这段草必须被它们合力切掉。我们讨论「上一辆跑向哪个方向」和「当前这辆跑向哪个方向」的四种情况，合法的就转移。

细节见代码。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,INF=1e9;
int n,x[N],p[N],d[N];
int f(int i,int s){//把状态 0/1 映射到方向 -1/+1 
	int w=(s==0?-1:1);
	return w==d[i]?0:1;
}
int dp[N][2],ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>x[i]>>p[i]>>d[i];
	dp[1][0]=f(1,0);
	dp[1][1]=f(1,1);
	for(int i=2;i<=n;++i){
		dp[i][0]=dp[i][1]=INF;//初始化 
		int diff=x[i]-x[i-1];
		//右->右 
		if(p[i-1]>=diff && dp[i-1][1]<INF)
			dp[i][1]=min(dp[i][1],dp[i-1][1]+f(i,1));
		//左->左	
		if(p[i]>=diff && dp[i-1][0]<INF)
			dp[i][0]=min(dp[i][0],dp[i-1][0]+f(i,0));
		//右->左 
		if(p[i-1]+p[i]>=diff && dp[i-1][1]<INF)
			dp[i][0]=min(dp[i][0],dp[i-1][1]+f(i,0));
		//左->右 不合法 
	}
	ans=min(dp[n][0],dp[n][1]);
	cout<<(ans>=INF?-1:ans);//INF无解 
	return 0;
}

完结撒花