Skip to content

「USACO 2004 Open (Gold)」Turning in Homework

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

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

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

#输入格式

11 行:三个整数 C,HC, HBB,分别表示科目数量、走廊长度和车站位置。

22 行到 C+1C + 1 行:第 i+1i + 1 行有两个整数 XiX_iTiT_i,表示第 ii 份作业应该在 XiX_i 处提交,且该科目老师的下课时间为 TiT_i

#输出格式

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

#输入输出样例

样例输入 #1

4 10 3
8 9
4 21
3 16
8 12

样例输出 #1

22

样例解释 #1

走到坐标 88 处,第 99 分钟交一本作业,等到第 1212 分钟时,交另一本作业。再走到坐标 44 处交作业,最后走到坐标 33 处,交最后一本作业,此地就是车站所在位置,共用时 2222 分钟。

#数据范围与提示

对于 100%100\% 的数据,1C,H10001 \leq C, H \leq 10000BH0 \leq B \leq H

#思路

区间 DP。

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

fi,j,0=min{max(fi1,j,0+xixi1,ti)max(fi,j+1,1+xj+1xi,ti)fi,j,1=min{max(fi1,j,0+xjxi1,tj)max(fi,j+1,1+xj+1xj,tj)\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}

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

mini=1C{min(fi,i,0,fi,i,1)+bxi}\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;
}