自动搬运

查看原文

来自洛谷，原作者为

	chenzefan 蒟蒻一枚||六年级||五级钩||GESP七级

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

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

以下是正文

提供一篇 C++ 的题解。

题目传送门

涉及知识

• 动态规划基础与转移。

思路分析

本人没有尝试暴力做法，用 dfs 暴力，应该可以拿点分。

来看正解，一眼题目用动态规划，因为容易发现，第 $i$ 根柱子的状态可以由第 $i-1$ 根柱子的状态进行转移。

状态定义——定义一个 dp[N][2]，dp[i][0] 表示不用传送门到达 $i$ 号柱子底部的时间，dp[i][1] 表示使用传送门到达 $i$ 号柱子底部的时间。

此部分代码：

double dp[N][2];

状态初始化——因为求最小值 $\min$，所以初始值要赋极大值，本人赋值了 0x3f，可供参考。还有，因为原点到第1根柱子之间没有传送门，所以 dp[1][0] 和 dp[1][1] 也要初始化为 $x_1$。

此部分代码：

memset(dp,0x3f,sizeof(dp)); 
dp[0][0]=0;
dp[1][0]=dp[1][1]=x[1];

状态转移——枚举每一个柱子：

• 如果不走传送门：用 dp[i-1][0] 和 dp[i-1][1] 的较小值 $\min$ 加上横坐标之差进行转移。
• 如果要走传送门：则要先减去传送门起点到底部所需时间，再加上使用传送门的时间，因为要更新到 $i$ 号柱子底部的最少时间，所以还要加上传送门终点到底部的时间。

此部分代码：

for(int i=2;i<=n;i++){//按照题目描述计算时间
		//不用传送门（直接转移） 
		dp[i][0]=min(dp[i-1][1]+x[i]-x[i-1],dp[i-1][0]+x[i]-x[i-1]);
		//使用传送门
		double last=0;
		if(a[i-1]<b[i-2]) last=(b[i-2]-a[i-1])/1.3;
		else last=(a[i-1]-b[i-2])/0.7;
		dp[i][1]=min(dp[i-1][0]+a[i-1]/0.7+b[i-1]/1.3,dp[i-1][1]-b[i-2]/1.3+last+b[i-1]/1.3);
	}

最后求时间只需按照题目描述模拟即可。输出即求到达第 $n$ 根柱子的最小方案，也就是 min(dp[n][0],dp[n][1])。

此部分代码：

printf("%.2lf",min(dp[n][0],dp[n][1]));//输出答案 

注意: dp 数组类型为 double。输出要保留两位小数

如果还没听懂请看代码。

代码（完整版）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],b[N],x[N];
double dp[N][2];//状态定义 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",x+i);
	for(int i=1;i<n;i++) scanf("%d%d",a+i,b+i);
	//状态初始化
	memset(dp,0x3f,sizeof(dp)); 
	dp[0][0]=0;
	dp[1][0]=dp[1][1]=x[1];
	//状态转移 
	for(int i=2;i<=n;i++){//按照题目描述计算时间
		//不用传送门（直接转移） 
		dp[i][0]=min(dp[i-1][1]+x[i]-x[i-1],dp[i-1][0]+x[i]-x[i-1]);
		//使用传送门
		double last=0;
		if(a[i-1]<b[i-2]) last=(b[i-2]-a[i-1])/1.3;
		else last=(a[i-1]-b[i-2])/0.7;
		dp[i][1]=min(dp[i-1][0]+a[i-1]/0.7+b[i-1]/1.3,dp[i-1][1]-b[i-2]/1.3+last+b[i-1]/1.3);
	}
	printf("%.2lf",min(dp[n][0],dp[n][1]));//输出答案 
	return 0; 
}