「USACO 2004 Open (Gold)」Turning in Homework

#题面

#题目描述

Bessie 有 $C$ 门科目的作业要上交，之后她要去坐巴士和奶牛同学回家。

每门科目的老师所在的教室排列在一条长为 $H$ 的走廊上，他们只在课后接收作业，交作业不需要时间。Bessie 现在在位置 $0$，她会告诉你每个教室所在的位置，以及走廊出口的位置。她 $1$ 秒钟可以走 $1$ 个单位的路程。她希望你计算最快多久以后她能交完作业并到达出口。

#输入格式

第 $1$ 行：三个整数 $C, H$ 和 $B$，分别表示科目数量、走廊长度和车站位置。

第 $2$ 行到 $C + 1$ 行：第 $i + 1$ 行有两个整数 $X_i$ 和 $T_i$，表示第 $i$ 份作业应该在 $X_i$ 处提交，且该科目老师的下课时间为 $T_i$。

#输出格式

单个整数，表示 Bessie 交完作业后走到车站的最短时间。

#输入输出样例

样例输入 #1

4 10 3
8 9
4 21
3 16
8 12

样例输出 #1

22

样例解释 #1

走到坐标 $8$ 处，第 $9$ 分钟交一本作业，等到第 $12$ 分钟时，交另一本作业。再走到坐标 $4$ 处交作业，最后走到坐标 $3$ 处，交最后一本作业，此地就是车站所在位置，共用时 $22$ 分钟。

#数据范围与提示

对于 $100\%$ 的数据，$1 \leq C, H \leq 1000$，$0 \leq B \leq H$。

#思路

区间 DP。

设 $f_{i, j, 0/1}$ 表示整段区间中除了 $i \sim j$ 段以外的部分都完成了之后，下一步要提交 $i$ 点或者 $j$ 点的作业时的最短用时。有转移方程：

$$\begin{aligned} f_{i, j, 0} &= \min\begin{cases} \max(f_{i - 1, j, 0} + x_i - x_{i - 1}, t_i) \\ \max(f_{i, j + 1, 1} + x_{j + 1} - x_i, t_i) \\ \end{cases} \\ f_{i, j, 1} &= \min\begin{cases} \max(f_{i - 1, j, 0} + x_j - x_{i - 1}, t_j) \\ \max(f_{i, j + 1, 1} + x_{j + 1} - x_j, t_j) \\ \end{cases} \end{aligned}$$

最后枚举结束点寻找最优答案即可：

$$\min_{i = 1}^{C} \{\min(f_{i, i, 0}, f_{i, i, 1}) + |b - x_i|\}$$

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <limits>
#include <utility>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1005;

int c, h, b, f[N][N][2], ans = std::numeric_limits<int>::max();
std::pair<int, int> a[N];

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(f, 0x3f, sizeof(f));

    cin >> c >> h >> b;

    for (int i = 1; i <= c; i++) {
        cin >> a[i].first >> a[i].second;
    }

    std::sort(a + 1, a + 1 + c);

    f[0][c][0] = f[0][c][1] = 0;

    for (int i = 1; i <= c; i++) {
        for (int j = c; j >= i; j--) {
            f[i][j][0] = std::min({
                std::max(f[i - 1][j][0] + a[i].first - a[i - 1].first, a[i].second),
                std::max(f[i][j + 1][1] + a[j + 1].first - a[i].first, a[i].second),
            });

            f[i][j][1] = std::min({
                std::max(f[i - 1][j][0] + a[j].first - a[i - 1].first, a[j].second),
                std::max(f[i][j + 1][1] + a[j + 1].first - a[j].first, a[j].second),
            });
        }
    }

    for (int i = 1; i <= c; i++) {
        ans = std::min(ans, std::min(f[i][i][0], f[i][i][1]) + std::abs(b - a[i].first));
    }

    cout << ans << endl;

    return 0;
}