思路:通过每行最优步数累加,求出全局最优步数 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
*/