글 읽기 - 트레이스백 부분만 문제 있는 건지 봐줄 수 있나요

jiyolla 3년 전 0

거의 또 6시간째 붙잡고 있는데, 해결이 안 되네요...

그냥 거리합은 제대로 구하고 있는 거 맞나요?

맞다면 거쳐온 경로 구하는 부분 어떻게 좀 쉽게 할 수 있을까요? 지금 뭔가 굉장히 복잡하게 구하고 있는 거 같네요... 복잡하니까 디버깅도 머리 아프네요...(이미 수차례 한 건데, 하면 할 수록 복잡해지네요...)

import sys
import math


def solve():
    read = sys.stdin.readline
    n = int(read())
    w = int(read())
    work = [list(map(int, read().split())) for _ in range(w)]

    def dist(p, q):
        return abs(p[0] - q[0]) + abs(p[1] - q[1])

    # dp[i][j] = minimal distance travelled
    # for first car ending up in ith work and second car ending up in jth work
    # But in fact, we do not need a 2-dimensial array, as a car is always going be on the last work
    # so a trick here
    # dp[i][j] = minimal distance travelled
    # where i = 0 stand for first car ending up in last work and i = 1 vice versa
    # j stand for the last work the other car is end up.
    # Note that, j = 0 means initial position rather than the first work.
    """
    dp = [[None] for _ in range(2)]
    dp[0][0] = dist(work[0], (1, 1))
    dp[1][0] = dist(work[0], (n, n))

    # Tackle ith work(i: direct index at work)
    for i in range(1, w):
        new_dp = [[math.inf] * (i + 1) for _ in range(2)]

        # first car engage
        for j in range(i):
            new_dp[0][j] = dp[0][j] + dist(work[i], work[i - 1])
        new_dp[0][i] = dp[1][0] + dist(work[i], (1, 1))
        for k in range(1, i):
            d = dp[1][k] + dist(work[i], work[k - 1])
            if d < new_dp[0][i]:
                new_dp[0][i] = d

        # second car engage
        for j in range(i):
            new_dp[1][j] = dp[1][j] + dist(work[i], work[i - 1])
        new_dp[1][i] = dp[0][0] + dist(work[i], (n, n))
        for k in range(1, i):
            d = dp[0][k] + dist(work[i], work[k - 1])
            if d < new_dp[1][i]:
                new_dp[1][i] = d
        dp = new_dp
    print(min(min(dp[0]), min(dp[1])))
    """

    # Now deal with traceback
    # Fuck, undoing the trick on state definition seems to be the easiet solution
    # Define dp as straight forward 2d array
    # dp[i][j] = min dist for first car at ith work, second car at jth work,
    # i == j == 0 means initial at position rather at work.
    dp = [[math.inf] * (w + 1) for _ in range(w + 1)]
    dp[1][0] = dist(work[0], (1, 1))
    dp[0][1] = dist(work[0], (n, n))

    # Tackle ith work(i: direct index at work)
    for i in range(1, w):
        # first car engage
        for j in range(i):
            dp[i + 1][j] = dp[i][j] + dist(work[i], work[i - 1])
        dp[i + 1][i] = dp[0][i] + dist(work[i], (1, 1))
        for k in range(1, i):
            d = dp[k][i] + dist(work[i], work[k - 1])
            if dp[i + 1][i] > d:
                dp[i + 1][i] = d

        # second car engage
        for j in range(i):
            dp[j][i + 1] = dp[j][i] + dist(work[i], work[i - 1])
        dp[i][i + 1] = dp[i][0] + dist(work[i], (n, n))
        for k in range(1, i):
            d = dp[i][k] + dist(work[i], work[k - 1])
            if dp[i][i + 1] > d:
                dp[i][i + 1] = d

    a, b, ans = 0, 0, math.inf
    for i in range(w + 1):
        for j in range(w + 1):
            if i == w or j == w:
                if ans > dp[i][j]:
                    a, b, ans = i, j, dp[i][j]
    print(ans)

    def traceback(last_car, last_work, pre_last_work):
        pre_last_car = next_last_car = 3 - last_car
        next_last_work = 0
        if last_work == 0:
            return [str(pre_last_car)] * pre_last_work
        if last_car == 2:
            ans = dp[0][last_work] + dist((1, 1), work[pre_last_work - 1])
            for i in range(1, last_work):
                d = dp[i][last_work] + dist(work[i - 1], work[pre_last_work - 1])
                if ans > d:
                    next_last_work, ans = i, d
        else:
            ans = dp[last_work][0] + dist((n, n), work[pre_last_work - 1])
            for i in range(1, last_work):
                d = dp[last_work][i] + dist(work[i - 1], work[pre_last_work - 1])
                if ans > d:
                    next_last_work, ans = i, d
        print_buf = [str(pre_last_car)] * (pre_last_work - last_work)
        return print_buf + traceback(next_last_car, next_last_work, last_work)

    print('\n'.join(traceback(2 if a > b else 1, b if a > b else a, w)[::-1]))


solve()

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

트레이스백 부분만 문제 있는 건지 봐줄 수 있나요

jiyolla 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말