鱼骨探矿的题解

原题描述：

题目描述：

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

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

经过初步探测，在第 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?

数据规模：

,

题目大意：?

叫你从（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;
}