洛谷 P3842 [TJOI2007]线段

题目传送门

f[i][1/0]表示到第i列左右端点的最短路程长度

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

int n,l[20001],r[20001],f[20001][2];

inline int min(int a,int b) {
    if(a < b) return a;
    return b;
}

int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n; i++)
        scanf("%d%d",&l[i],&r[i]);
    f[1][1] = r[1] - 1;
    f[1][0] = r[1] - 1 + r[1] - l[1];
    for(int i = 2;i <= n; i++) {
        int u = abs(r[i] - l[i]) + 1;
        f[i][1] = min(f[i-1][1] + abs(r[i-1] - l[i]),f[i-1][0] + abs(l[i-1] - l[i])) + u;
        f[i][0] = min(f[i-1][1] + abs(r[i-1] - r[i]),f[i-1][0] + abs(l[i-1] - r[i])) + u;
    }
    printf("%d",min(f[n][1] + abs(n - r[n]),f[n][0] + abs(n - l[n])));    
    return 0;
}