P3842 [TJOI2007] 线段

洛谷-题目链接

[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;
}