鱼骨探矿的题解

2023-12-13 06:24:38

原题描述:

题目描述:

众所周知,《我的世界》中一种非常流行的探矿方式就是鱼骨探矿。

我的世界的地图可以看作一个n \times n的正方形世界。

经过初步探测,在第 i 行,[li, ri] 区间内可能存在宝藏。为了探索效率,我们要从 (1,1) 遍历到 (n,n),并且每一步只能往下或者往左或者往右(不能往上);为了不错过宝藏,我们需要保证每一行的区间都被遍历过。也就是说你必须遍历完一行的区间之后才能往下走到下一行。

问遍历结束最少需要多少步。

输入格式:

第一行一个整数 n,

接下来 n 行每行两个整数,表示 li 和 ri。

输出格式:

输出一个整数,表示最少步数。

样例输入:

6

2 6

3 4

1 3

1 2

3 6

4 5

样例输出:

24?

数据规模:

n\le2\times 10^4,1 \le L_i\le R_i\le n

题目大意:?

叫你从(1,1)遍历到(n,n),要走过每行的区间。

主要思路:

这题是一道dp题,我们考虑两个方面:

1.dp的转态设计

dp[i][j]表示:从第i行到第i+1行,从左边下(j=0)还是从右边下(j=1),用的最小步数。

2.dp的转移:

如果从左边下来(dp[i][0]):就是从

min(dp[i-1][0]+calc(a[i-1].x,a[i].y)+calc(a[i].x,a[i].y),dp[i-1][1]+calc(a[i-1].y,a[i].y)+calc(a[i].x,a[i].y))+1;转移过来,其中x是左边的下标,y是右边的下标,calc(a,b)是abs(a-b),所以这里的calc(a[i-1].x,a[i].y)代表从上面得左边走到这行的右边(由于前面是dp[i-1][0]所以是从左边下)calc(a[i].x,a[i].y)就是这段区间的距离。calc(a[i-1].y,a[i].y)就是从上面的右边走到第i行的右边(前面是dp[i-1][1])。

同理,从右边下来(dp[i][1])就是:min(dp[i-1][0]+calc(a[i-1].x,a[i].x)+calc(a[i].x,a[i].y),dp[i-1][1]+calc(a[i-1].y,a[i].x)+calc(a[i].x,a[i].y))+1;

最后上代码:

代码:

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
pair<int,int> a[20010];
int dp[20010][2];//第i-1行到第i行,从左边下还是从右边下,用的最少步数 
int calc(int a,int b)
{
	return abs(a-b);
 } 
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
	 } 
	dp[1][0] = calc(1,a[1].y)+calc(a[1].x,a[1].y);
	dp[1][1] = calc(1,a[1].y);
	for(int i=2;i<=n;i++)
	{
		dp[i][0] = min(dp[i-1][0]+calc(a[i-1].x,a[i].y)+calc(a[i].x,a[i].y),dp[i-1][1]+calc(a[i-1].y,a[i].y)+calc(a[i].x,a[i].y))+1;//左边下来
		dp[i][1] = min(dp[i-1][0]+calc(a[i-1].x,a[i].x)+calc(a[i].x,a[i].y),dp[i-1][1]+calc(a[i-1].y,a[i].x)+calc(a[i].x,a[i].y))+1;//右边下来
	}
	cout<<min(dp[n][0]+calc(a[n].x,n),dp[n][1]+calc(a[n].y,n));
	return 0;
}

文章来源:https://blog.csdn.net/a613322/article/details/134956607
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。