题目链接

luogu [TJOI2007]线段

题解

dp[i][0/1]第i行在左/右端点的最短路

瞎转移

代码

#include<bits/stdc++.h>

using namespace std;

inline int read()  {

    int x= 0 ,f = 1;

    char c = getchar();

    while(c < '0' || c > '9')c = getchar();

    while(c <= '9' &&c >= '0')x = x * 10 + c - '0',c = getchar();

    return x * f;

}

const int maxn = 500007;

int n;

int l[maxn],r[maxn],dp[maxn][2];

int main() {

    n = read();

    for(int i = 1;i <= n;++ i)   l[i] = read(),r[i] = read();

    dp[1][0] = r[1] + r[1] - l[1] - 1;

    dp[1][1] = r[1] - 1;

    for(int i = 2;i <= n;++ i) {

    	int x = dp[i - 1][0],y = dp[i - 1][1];

       	dp[i][0] = min(x + abs(l[i-1] - r[i]) + r[i] - l[i] + 1, y + abs(r[i-1] - r[i]) + r[i] - l[i] + 1);

       	dp[i][1] = min(x + abs(l[i-1] - l[i]) + r[i] - l[i] + 1, y + abs(r[i-1] - l[i]) + r[i] - l[i] + 1);

    }

    printf("%d\n",min(dp[n][0] + n - l[n], dp[n][1] + n - r[n]));

    return 0;

}