题解 P3842 【[TJOI2007]线段】

wtxy2006 · 2020-04-03 22:08:12 · 题解

题目大意：

有 n 条线段，要求从上至下走完所有的线段并且使路程最短，求最短的距离。

题目分析：

显然是动态规划的水题，定义状态 f[i][0] 表示已走完第 i 列的线段，并且在线段的左端点，f[i][1] 表示已走完第 i 列，且在线段的右段点。

考虑转移，发现当前行的状态只和上一行的状态有关，则：

• 走完这行在这行的右端点：从上一行的左端点到这一行的左端点的距离,和从上一行的右段点到这一行的左端点的距离中的最小值加一(上下移动所花费的距离)再加上这条线段的长度。 f[i][1] = \min(f[i - 1][0] + abs(ls[i - 1] - ls[i]),f[i - 1][1] + abs(rs[i - 1] - ls[i])) + l[i] + 1;
• 走完这行在这行的左端点：从上一行的左端点到这一行的右端点的距离,和从上一行的右段点到这一行的右端点的距离中的最小值加一(上下移动所花费的距离)再加上这条线段的长度。 f[i][0] = \min(f[i - 1][0] + abs(ls[i - 1] - rs[i]),f[i - 1][1] + abs(rs[i - 1] - rs[i])) + l[i] + 1

空间还可以用滚动数组继续优化，首先规定：

#define pre(i) ((i + 1) % 2)
#define now(i) (i % 2)

所以可将转移方程改成这样：

所以只要 4 个 int 空间就可以存下所有的状态。

完整代码：

// P3842 [TJOI2007]线段
#include <cmath>
#include <cstdio>
#include <iostream>
#define MN 20005
#define pre(i) ((i + 1) % 2)
#define now(i) (i % 2)
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return x * f;
}
int n, ls[MN], rs[MN], f[2][2], l[MN];
int main() {
  n = read() - 1;
  for (int i = 0; i <= n; i++)
    ls[i] = read(), rs[i] = read(), l[i] = rs[i] - ls[i];
  f[0][0] = rs[0] + l[0], f[0][1] = ls[0] + l[0];
  for (int i = 1; i <= n; i++)
    f[now(i)][0] = min(f[pre(i)][0] + abs(ls[i - 1] - rs[i]),
                       f[pre(i)][1] + abs(rs[i - 1] - rs[i])) +
                   l[i] + 1,
    f[now(i)][1] = min(f[pre(i)][0] + abs(ls[i - 1] - ls[i]),
                       f[pre(i)][1] + abs(rs[i - 1] - ls[i])) +
                   l[i] + 1;
  printf("%d\n", min(f[now(n)][0] - ls[n], f[now(n)][1] - rs[n]) + n);
  return 0;
}

时间复杂度 O(n)。