简单DP
思路
1.状态表示:f[N][2],其中f[i][0]表示到达第i行的左端点所需的最小步数,f[i][1]表示到达第i行的右端点所需的最小步数
2.状态转移:
f[i][0]=min(f[i-1][0]+dis(l[i-1]-l[i]),f[i-1][1]+dis(r[i-1],l[i]))+r[i]-l[i]+1
f[i][1]=min(f[i-1][0]+dis(l[i-1]-r[i]),f[i-1][1]+dis(r[i-1],r[i]))+r[i]-l[i]+1
3.边界情况
f[1][1]=r[1]-1
f[1][0]=(r[1]-1)+(r[1]-l[1])
代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=2e4+10;
int n,f[N][2];
int l[N],r[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int l1,r1;
cin>>l1>>r1;
l[i]=l1;
r[i]=r1;
}
f[1][1]=r[1]-1;
f[1][0]=(r[1]-l[1])+(r[1]-1);
for(int i=2;i<=n;i++)
{
f[i][0]=min(f[i-1][0]+abs(l[i-1]-r[i]),f[i-1][1]+abs(r[i-1]-r[i]))+1+r[i]-l[i];
f[i][1]=min(f[i-1][0]+abs(l[i-1]-l[i]),f[i-1][1]+abs(r[i-1]-l[i]))+1+r[i]-l[i];
}
cout<<min(f[n][0]+n-l[n],f[n][1]+n-r[n])<<endl;
return 0;
}