Как можно решить проблему 915. Кубик - 2 acmp?

Question

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 тесткейсе (Time limie exceeded), помогите с оптимизацией моего кода, или буду рад если покажете другое решение

Вначале я перебрал все стороны кубика чтобы получить максимальное число индексе (0,0)

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

После открыл map где я указал соседей каждой стороны кубика:

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)
}

В этой задаче мне надо максимизировать сумму перекатывая кубик на соседние стороны, то есть сторона_кубика*число(х,у) Дальше мне нужно добраться от (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]))

Answer 1

Первый и последний раз эту задачу сдали на Питоне в 2019 году. Сложно.

Ограничение по памяти требуют чтобы поле обрабатывалось по строкам. Ограничения по времени требуют оптимизировать расчёт максимумов (две противолежащие стороны используют общий максимум по "поясу" из клеток их разделяющих.

def main():
    belts = (1, 2, 3, 4), (0, 2, 3, 5), (0, 1, 4, 5)
    cube = 0, 1, 2, 2, 1, 0

    n, m = map(int, input().split())

    def maxes(g):
        s = tuple(g)
        return [max(s[f] for f in faces) for faces in belts]

    mx = [[0] * 3] * m

    row = list(map(int, input().split()))

    mx[0] = maxes((p + 1) * row[0] for p in range(len(cube)))

    for j in range(1, m):
        mx[j] = maxes(
            (p + 1) * row[j] + mx[j - 1][b] for p, b in enumerate(cube)
        )

    for _ in range(1, n):
        row = list(map(int, input().split()))

        mx[0] = maxes(
            (p + 1) * row[0] + mx[0][b] for p, b in enumerate(cube)
        )

        for j in range(1, m):
            mx[j] = maxes(
                (p + 1) * row[j] + max(mx[j][b], mx[j - 1][b])
                for p, b in enumerate(cube)
            )

    print(max(mx[m - 1]))


main()

Если продолжать рефакторить код можно получить трёхкратный запас по скорости:

def main():
    n, m = map(int, input().split())

    mx0 = [0] + [float('-inf')] * m
    mx1 = mx0[:]
    mx2 = mx1[:]

    for _ in range(n):
        for j, a in enumerate(map(int, input().split())):
            s0 = (1, 6)[a > 0] * a + max(mx0[j - 1], mx0[j])
            s1 = (2, 5)[a > 0] * a + max(mx1[j - 1], mx1[j])
            s2 = (3, 4)[a > 0] * a + max(mx2[j - 1], mx2[j])
            mx0[j] = max(s1, s2)
            mx1[j] = max(s2, s0)
            mx2[j] = max(s0, s1)

    print(max(mx0[m - 1], mx1[m - 1], mx2[m - 1]))


main()

БЛОГ НА HUSL

Как можно решить проблему 915. Кубик - 2 acmp?

Ответы (1 шт):