自动搬运

查看原文

来自洛谷，原作者为

	Huami360 菜是原罪

搬运于2025-08-24 21:53:17，当前版本为作者最后更新于2018-07-18 15:49:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

裸DP。感觉楼下的好复杂，我来补充一个易懂的题解。

f[i][0]表示走完第i行且停在第i行的左端点最少用的步数

f[i][1]同理，停在右端点的最少步数。

那么转移就很简单了，走完当前行且停到左端点，那么一定是从右端点过来的，那么从上一行左端点转移的话就是

f[i][0]=abs(上一行左端点的坐标-本行右端点的坐标+本行线段长度)

从上一行右端点转移同理。 不需要什么判断。边界f[1][0]=r[1]+r[1]-l[1]-1,f[1][1]=r[1]-1，然后直接搞就行了，时间复杂度O(n)。

#include <iostream>
#include <cstdio>
#define rep(i,m,n) for(int i=m;i<=n;++i)
using namespace std;
inline int read(){
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();
    return s * w;
}
const int MAXN = 20010;
int n;
int l[MAXN], r[MAXN], f[MAXN][2];
int main(){
    n = read();
    rep(i, 1, n) l[i] = read(), r[i] = read();
    f[1][0] = r[1] + r[1] - l[1] - 1;
    f[1][1] = r[1] - 1;
    rep(i, 2, n)
       f[i][0] = min(f[i-1][0] + abs(l[i-1] - r[i]) + r[i] - l[i] + 1, f[i-1][1] + abs(r[i-1] - r[i]) + r[i] - l[i] + 1),
       f[i][1] = min(f[i-1][0] + abs(l[i-1] - l[i]) + r[i] - l[i] + 1, f[i-1][1] + abs(r[i-1] - l[i]) + r[i] - l[i] + 1);
    printf("%d\n", min(f[n][0] + n - l[n], f[n][1] + n - r[n]));
    //rep(i, 1, n){ rep(j, 0, 1) printf("f[%d][%d] = %d, ", i, j, f[i][j]); puts(""); }
    return 0;
}