主页 / user-656912

Alisher's questions

Martin Hope
Alisher
Asked: 2024-11-27 16:42:49 +0000 UTC
  • 7

https://acmp.ru/index.asp?main=task&id_task=915

我尝试解决这个问题的方法如下：

N, M = map(int, input().split())
field = [[] for _ in range(N)]
for i in range(N):
    field[i] = list(map(int, input().split()))

dp = [[[-float('inf')] * 7 for _ in range(M)] for _ in range(N)]

for k in range(1, 7):
    dp[0][0][k] = k * field[0][0]
adjacent_faces = {
    1: (2, 3, 4, 5),
    2: (1, 3, 4, 6),
    3: (1, 2, 5, 6),
    4: (1, 2, 5, 6),
    5: (1, 3, 4, 6),
    6: (2, 3, 4, 5)
}

for i in range(N):
    for j in range(M):
        for k in range(1, 7):

            if i + 1 < N:
                for face in adjacent_faces[k]:
                    dp[i + 1][j][face] = max(dp[i + 1][j][face], dp[i][j][k] + face * field[i + 1][j])

            if j + 1 < M:
                for face in adjacent_faces[k]:
                    dp[i][j + 1][face] = max(dp[i][j + 1][face], dp[i][j][k] + face * field[i][j + 1])
result = max(dp[N - 1][M - 1][k] for k in range(1, 7))
print(result)

卡在测试用例 34 上（超出时间限制），请帮助我优化我的代码，或者如果您向我展示另一个解决方案，我会很高兴

首先，我遍历了立方体的所有面以获得最大索引号（0,0）

for k in range(1, 7):
    dp[0][0][k] = k * field[0][0]

然后我打开地图，在其中指示立方体每一面的邻居：

adjacent_faces = {
    1: (2, 3, 4, 5),
    2: (1, 3, 4, 6),
    3: (1, 2, 5, 6),
    4: (1, 2, 5, 6),
    5: (1, 3, 4, 6),
    6: (2, 3, 4, 5)
}

在这个问题中，我需要通过将立方体滚动到相邻边来最大化总和，即，cube_side*number(x,y) 然后我需要从 (0,0) 到 (N-1,M-1) ，但我只能向下向右对获得的值进行求和。在循环内我查看立方体的所有面

for k in range(1,7)

然后我尝试与邻居的所有可能的组合以最大化总和

for face in adjacent_faces[k]

然后我总结所有的值

抱歉没有立即解释所有内容。

我尝试了这种方法，但在测试用例 33 上失败了

from collections import deque

N, M = map(int, input().split())
field = [list(map(int, input().split())) for _ in range(N)]

adjacent_faces = {
    1: (2, 3, 4, 5),
    2: (1, 3, 4, 6),
    3: (1, 2, 5, 6),
    4: (1, 2, 5, 6),
    5: (1, 3, 4, 6),
    6: (2, 3, 4, 5),
}
dp = [[[-float('inf')] * 7 for _ in range(M)] for _ in range(N)]

queue = deque()

for k in range(1, 7):
    dp[0][0][k] = k * field[0][0]
    queue.append((0, 0, k))

while queue:
    x, y, k = queue.popleft()
    for dx, dy in ((1, 0), (0, 1)):
        nx, ny = x + dx, y + dy
        if 0 <= nx < N and 0 <= ny < M:
            for face in adjacent_faces[k]:
                new_value = dp[x][y][k] + face * field[nx][ny]
                if new_value > dp[nx][ny][face]:
                    dp[nx][ny][face] = new_value
                    queue.append((nx, ny, face))
print(max(dp[N - 1][M - 1]))
python