2020-2021 ACM-ICPC Asia Seoul Regional Contest D.Electric Vehicle

二维平面上有 $n$ 个点$(x_i, y_i)$. 有一辆电汽车, 电池容量为 $W$, 要从点 $s$ 到点 $t$. 每个点都可以充电, 充一个单位的电量需要 $c_i$ 点花费. 一个单位的电量能走一个单位距离. 两个点之间的距离是笛卡尔距离. 开始时车在 $s$ 点电量为 $0$, 问在充电次数不超过 $\Delta$ 的情况下, 到达 $t$ 点的最小花费.

$1 \le n \le 1000, 0 \le x_i, y_i \le 10^6, 1 \le c_i \le 10^4, 1 \le W \le 10^5, 1 \le \Delta \le 10$

首先想到经典贪心题. 确定一条路线, 那么一定是两种选择:

1. 充满电往下走
2. 充到刚好到下一个点

根据这两个决策, 我们设计dp.

$dp(i, x, 0)$ 表示已经充了 $i$ 次电, 当前在点 $x$, 从某个点充到刚好能过来, 即现在的电量为 $0$.

$dp(i, x, y)$ 表示已经充了 $i$ 次电, 当前在点 $x$, 从 $y$ 充满了电过来, 即现在的电量为 $W - dist(y, x)$.

方程很好写:

$$ \begin{aligned} dp(i, x, 0) &= \min_{y \ne x}^{dist(y, x) \le W} \{ dp(i-1, y, 0) + c_y \cdot dist(y, x) \} \\ dp(i, x, 0) &= \min_{y, z \ne x}^{dist(z, y) \le W, W - dist(z, y) \le dist(y, x)} \{ dp(i-1, y, z) + c_y \cdot (dist(y, x) - (W - dist(z, y))) \} \\ dp(i, x, y) &= \min_{y \ne x}^{dist(y, x) \le W} \{ dp(i-1, y, 0) + c_y \cdot W \} \\ dp(i, x, y) &= \min_{y, z \ne x}^{dist(y, x) \le W} \{ dp(i-1, y, z) + c_y \cdot dist(z, y) \} \end{aligned} $$

第一个和第三个可以$O(n^2)$完成, 第四个也可以设$f(i, y) = \min \{ dp(i-1, y, x) + c_y \cdot dist(z, y) \}$在$O(n^2)$内转移$dp(i, x, y) = f(i-1, y)$

第二个方程的优化是一个难点.

变一下型:

$$ \begin{aligned} dp(i, x, 0) &= \min_{y, z \ne x}^{dist(z, y) \le W, W - dist(z, y) \le dist(y, x)} \{ dp(i-1, y, z) + c_y \cdot (dist(y, x) - (W - dist(z, y))) \} \\ &= \min_{y \ne x}^{dist(y, x) \le W} \{ \min_{z \ne y}^{dist(z, y) \le W} \{ dp(i-1, y, z) - c_y \cdot (W - dist(y, z)) \} + c_y \cdot dist(y, x) \} \end{aligned} $$

然后有一个技巧. 看没变形的那个方程, 当 $dist(y, x) < W - dist(z, y)$ 时, 是不会更新 $dp(i, x, 0)$ 的. 运用一下排序的技巧, 如果让 $dist(y, x)$ 递增, 那么"前面的"枚举对$(x, y)$“能转移"的 $(W - dist(z, y))$, “后面的"也一定能转移. 再看变形后的方程, 里面一层的 $\min$ 没有含 $x$ 的参数, 我们用另一个变量 $g$ 来表示里面一层 $\min$. 那么我们可以"同时枚举 $z$ 和 $x$”, 即"把 $x$ 当成里面一层 $\min$ 的 $z$”. 把$(W - dist(y, z))$ 和 $dist(y, x)$ 放在一起排序, 即把 $(W - dist(y, x))$ 和 $dist(y, x)$ 放在一起排序. 然后按照这个的排序顺序来枚举. 能够发现, $y$ 是连接两个 $\min$ 的桥梁, 所以我们把 $y$ 第一维枚举, 然后对 $n-1$ 个 $x$ (因为 $x \ne y$) 的 $(W - dist(y, x))$ 以及 $dist(y, x)$ 放在一起排序, 按照这个排序枚举这 $2(n-1)$ 个变量, 碰到 $W - dist(y, x)$ 就更新 $g$, 碰到 $dist(y, x)$ 就更新 $dp(i, x, 0)$.

排序可以$O(n^2)$预处理, 对每个 $y$ 排这 $2(n-1)$ 个变量, 存在 vector 里, 这样就把复杂度压下来了.

由于之前是先枚举$x$再枚举$y$的, 后面发现要先枚举$y$才能做这第二个方程, 然后前面写过的就乱了…总之, 注意细节, 想好再写, 否则得不偿失!

总复杂度$O(\Delta n^2)$

 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
55
56
57
58
59
60
61
62
63
64
65

const int MAXN = 1e3+10;
const int MAXD = 15;

struct Node {
	LL a;
	int flag, x, y;
	bool operator < (const Node &N) const {
		return a == N.a ? flag == N.flag ? x == N.x ? y < y : x < N.x : flag < N.flag : a < N.a;
	}
};

PII villages[MAXN];

LL dist(int i, int j) {
	return LL(abs(villages[i].first - villages[j].first) + abs(villages[i].second - villages[j].second));
}

int n, s, t, W, D, c[MAXN];
LL dp[MAXD][MAXN][MAXN], f[MAXD][MAXN];
vector<Node> v[MAXN];

int main() {
	scanf("%d", &n);
	s = 1, t = 2;
	for (int i = 1; i <= n; i++) {
		int x, y;
		scanf("%d%d%d", &x, &y, c + i);
		villages[i] = {x, y};
	}
	scanf("%d%d", &W, &D);

	memset(dp, 0x3f, sizeof(dp));
	memset(f, 0x3f, sizeof(f));
	dp[0][s][0] = 0;

	for (int y = 1; y <= n; y++) {
		for (int x = 1; x <= n; x++) if (y != x) {
			v[y].push_back(Node{dist(x, y), 1, x, y});
			if (dist(x, y) <= W)
				v[y].push_back(Node{W - dist(x, y), 0, x, y});
		}
		sort(v[y].begin(), v[y].end());
	}
	for (int i = 1; i <= D; i++)
		for (int y = 1; y <= n; y++) {
			LL g = INF;
			for (auto N : v[y]) {
				if (N.flag && dist(y, N.x) <= W)
						dp[i][N.x][0] = min(dp[i][N.x][0], g + c[y] * N.a);
				else if (dp[i-1][y][N.x] < INF)
					g = min(g, dp[i-1][y][N.x] - c[y] * N.a);
				if (dist(y, N.x) <= W) {
					f[i][N.x] = min(f[i][N.x], dp[i][N.x][y] + c[N.x] * dist(N.x, y));
					dp[i][N.x][y] = f[i-1][y];
					dp[i][N.x][y] = min(dp[i][N.x][y], dp[i-1][y][0] + c[y] * W);
					dp[i][N.x][0] = min(dp[i][N.x][0], dp[i-1][y][0] + c[y] * dist(N.x, y));
				}
			}
		}
	LL ans = INF;
	for (int i = 1; i <= D; i++)
		ans = min(ans, dp[i][t][0]);
	printf("%lld\n", ans < INF ? ans : -1);
	return 0;
}