CF1627E题解

· · 题解

思路

1.我们可以尝试着解一下 n 和 m 以及 k。

2.我们难道需要解所有的 n×m 的房间吗？

3.独立为每一行单独求解。

讲解

输入的建筑平面图包括 n×m 个房间，但在最坏的情况下是 10^{10}，这些房间大多数对我们来说都不重要。我们可以使用一个简化的建筑版本，最多包含 2k+2 个房间和每个阶梯的两个端点，以及起点和目标房间。

由于每个梯子连接一个较低的楼层和一个较高的楼层，并且是单向的，我们可以逐层处理房间，从第 1 层到第 n 层。在每一层，让我们按非降序排列所有房间。现在，我们可以使用动态规划以及前面提到的方法来计算到达所有重要房间的最小距离。

首先，我们使用同一楼层的房间作为中间层，计算到达每个房间的最低成本。我们可以通过在地板上的房间上迭代两次来实现这一点，一次从左到右，然后从右到左。然后，地板上的每个房间，如果有梯子从上面爬起来，我们可以更新梯子末端房间的 dp 值。

我们的要计算的是目标房间的dp值。

时间复杂度：O\left( k\log \left( k\right) \right)。

代码

import sys, os, io
from collections import defaultdict
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
inf = 5 * 10**16
for _ in range(int(input())):
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    go_to = defaultdict(list)
    coords = set()
    coords.add((1, 1))
    coords.add((n, m))
    for i in range(k):
        p, q, r, s, t = map(int, input().split())
        go_to[p * m + q] += [[r, s, t]]
        coords.add((p, q))
        coords.add((r, s))
    coords = sorted(list(coords))
    N, index = len(coords), {}
    dp, prefix, suffix = [-inf] * N, [-inf] * N, [-inf] * N
    for i in range(N): index[coords[i]] = i
    pairs, i = [], 0
    dp[0] = 0
    while i < N:
        j = i
        while j + 1 < N and coords[j + 1][0] == coords[j][0]:
            j += 1
            if coords[j][0] == 1:
                dp[j] = -a[0] * (coords[j][1] - 1)
        pairs += [(i, j)]
        i = j + 1
    for start, end in pairs:
        leftVal = rightVal = -inf
        for i in range(start, end + 1):
            x, y = coords[i]
            leftVal = max(leftVal, prefix[i])
            dp[i] = max(dp[i], leftVal - a[x - 1] * (y - 1))
        for i in range(end, start - 1, -1):
            x, y = coords[i]
            rightVal = max(rightVal, suffix[i])
            dp[i] = max(dp[i], rightVal - a[x - 1] * (m - y))
        for i in range(start, end + 1):
            if dp[i] == -inf: continue
            x, y = coords[i]
            for r, s, t in go_to[x * m + y]:
                j = index[(r, s)]
                dp[j] = max(dp[j], dp[i] + t)
                prefix[j] = max(prefix[j], dp[j] + a[r - 1] * (s - 1))
                suffix[j] = max(suffix[j], dp[j] + a[r - 1] * (m - s))
    print(-dp[-1] if dp[-1] != -inf else "NO ESCAPE")

100分结束。