自动搬运

查看原文

来自洛谷，原作者为

	Solwek 比唐挑战吗，那我赢了

搬运于2025-08-24 23:00:41，当前版本为作者最后更新于2024-07-09 18:26:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一道很神奇的题目，感觉什么算法都行。

由于 $n\le 1000$ 并且联系题目，我们很难不想到 $dp$，设 $f_{i,0}$ 表示已经来到第 $i$ 层，并且在左端点的最少时间，$f_{i,1}$ 表示已经来到第 $i$ 层，并且在右端点的最少时间。

状态转移显然，我们只需要枚举 $i$ 从左端点落到的板子编号和右端点落到的板子编号进行转移，以左端点举例：（设落下去的板子编号为 $j$）。

转移条件为 $j$ 是第一个满足 $l_j\le l_i\le r_j$ 并且 $h_i\ge h_j$ 条件的板子编号。

初值为 $f_{s,0}=0,f_{s,1}=r_s-l_s$。

但由于题目并未保证 $h_i\ge h_{i+1}$，所以我们要先排序，再 $dp$，并且 $s,t$ 也要变成新序列的编号。

时间复杂度应该是 $O(n^2)$。

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;

struct node{
	int l,r,h,id;
}a[1010];
int dp[1010][2];
bool cmp(node x,node y){
	if(x.h==y.h)return x.l<y.l;
	return x.h>y.h;
}
signed main(){	
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n,os,ot;
	cin>>n>>os>>ot;
	for(int i=1;i<=n;i++)
		cin>>a[i].l>>a[i].r>>a[i].h,a[i].id=i,dp[i][0]=dp[i][1]=1e18;
	sort(a+1,a+n+1,cmp);
	int s,t;
	for(int i=1;i<=n;i++){
		if(a[i].id==os)s=i;
		if(a[i].id==ot)t=i;
	}
	dp[s][0]=0,dp[s][1]=a[s].r-a[s].l;
	int ans=1e18;
	for(int i=s;i<=t;i++){
		for(int j=i+1;j<=t;j++){
			if(a[i].l>=a[j].l&&a[i].l<=a[j].r&&a[i].h>a[j].h){
				int val=a[i].h-a[j].h;
				if(j==t)ans=min(ans,dp[i][0]+val);
				dp[j][0]=min(dp[j][0],dp[i][0]+a[i].l-a[j].l+val);
				dp[j][1]=min(dp[j][1],dp[i][0]+a[j].r-a[i].l+val);
				break;
			}
		}
		for(int j=i+1;j<=t;j++){
			if(a[i].r>=a[j].l&&a[i].r<=a[j].r&&a[i].h>a[j].h){
				int val=a[i].h-a[j].h;
				if(j==t)ans=min(ans,dp[i][1]+val);
				dp[j][0]=min(dp[j][0],dp[i][1]+a[i].r-a[j].l+val);
				dp[j][1]=min(dp[j][1],dp[i][1]+a[j].r-a[i].r+val);
				break;
			}
		}
	}
	if(ans==1e18)cout<<"-1\n";
	else cout<<ans<<'\n';
	return 0;
}