72分求助
查看原帖
72分求助
379113
dtrthg楼主2023/4/29 15:00

思路:通过每行最优步数累加,求出全局最优步数 code:

#include <bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define of(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
const int mod=1e6+7;
const int Mod=1e9+7;
const int INF=0x3f3f3f3f;
const int Maxn=2e4+10;
//dp[i]表示第i层的最短路 
ll dp[Maxn];
int main()
{
	ll n;cin>>n;
	ll nowx=1;//nowx表示现在所处列数 
	fo(i,1,n)
	{
		ll le,ri;cin>>le>>ri;
		if(abs(le-nowx)<abs(ri-nowx))//如果左端点比右端点近 
		{
			dp[i]=abs(le-nowx)+(ri-le)+dp[i-1];//加上离左端点的距离、线段长度和上层步数 
			nowx=ri;//走到了右端点 
		}
		else
		{
			dp[i]=abs(ri-nowx)+(ri-le)+dp[i-1];
			nowx=le;
			//同理 
		}
	}
	ll ans=dp[n]+(n-nowx)+(n-1);//加上终点距离和下层步数 
	cout<<ans<<endl;
	return 0;
}
/*
in1:
6
2 6
3 4
1 3
1 2
3 6
4 5
out1:
24
*/

2023/4/29 15:00
加载中...