[TJOI2007] 线段
提示
我们选择的路线是
(1, 1) (1, 6)
(2, 6) (2, 3)
(3, 3) (3, 1)
(4, 1) (4, 2)
(5, 2) (5, 6)
(6, 6) (6, 4) (6, 6)
不难计算得到，路程的总长度是 24。
代码代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4+5;
int n;
//a[i][0] 表示 第i行的左端点
//a[i][1] 表示 第i行的右端点
//b[i] 表示每行线段的距离
int a[N][2],b[N];
int f[N][2]; //利用发f[i][0],f[i][1] 保存每行左右端点的最短距离
int dis(int x,int y) { //利用 dis() 计算每行的距离
return abs(x-y);
}
int main() {
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i][0]>>a[i][1];
b[i]=a[i][1]-a[i][0];
}
f[1][0]=dis(a[1][1],1)+b[1];
f[1][1]=dis(a[1][1],1);
for(int i=2; i<=n; i++) {
f[i][0]=min(f[i-1][0]+dis(a[i-1][0],a[i][1])+b[i],f[i-1][1]+dis(a[i-1][1],a[i][1])+b[i])+1;
f[i][1]=min(f[i-1][0]+dis(a[i-1][0],a[i][0])+b[i],f[i-1][1]+dis(a[i-1][1],a[i][0])+b[i])+1;
}
cout<<min(f[n][0]+dis(n,a[n][0]),f[n][1]+dis(n,a[n][1]));
return 0;
}