글 읽기 - 이 점화식 어디가 틀렸을까요..?

winnyiee 4년 전 0

최대한 반례를 만들어서 넣어봐도 어디가 잘못된지 모르겠네요..

dp[i][0]은 dp[i-1]에서 a가 움직였을 때의 작은 값

dp[i][1]은 dp[i-1]에서 b가 움직였을 때의 작은 값

으로 정의해봤는데 뭐가 오류일까요.. 어렵네요

n = int(input())
w = int(input())


dp = []
for i in range(w):
    dp.append([[[],[],0,[]],[[],[],0,[]]])





y,x = map(int,input().split())

dp[0][0] = [[y,x],[n,n],y+x-2,[1]]
dp[0][1] = [[1,1],[y,x],n-y+n-x,[2]]


for i in range(1,w):
    y,x = map(int,input().split())
    a = [dp[i-1][0][0][0],dp[i-1][0][0][1]]
    b = [dp[i-1][0][1][0],dp[i-1][0][1][1]]
    if abs(y-a[0])+abs(x-a[1])<=abs(y-b[0])+abs(x-b[1]):
        dp[i][0][0] = [y,x]
        dp[i][0][1] = b
        dp[i][0][2] = dp[i-1][0][2]+abs(y-a[0])+abs(x-a[1])
        dp[i][0][3] = dp[i-1][0][3]+[1]
    else:
        dp[i][0][0] = a
        dp[i][0][1] = [y,x]
        dp[i][0][2] = dp[i-1][0][2]+abs(y-b[0])+abs(x-b[1])
        dp[i][0][3] = dp[i-1][0][3]+[2]
        
    a = [dp[i-1][1][0][0],dp[i-1][1][0][1]]
    b = [dp[i-1][1][1][0],dp[i-1][1][1][1]]
    if abs(y-a[0])+abs(x-a[1])<=abs(y-b[0])+abs(x-b[1]):
        dp[i][1][0] = [y,x]
        dp[i][1][1] = b
        dp[i][1][2] = dp[i-1][1][2]+abs(y-a[0])+abs(x-a[1])
        dp[i][1][3] = dp[i-1][1][3]+[1]
    else:
        dp[i][1][0] = a
        dp[i][1][1] = [y,x]
        dp[i][1][2] = dp[i-1][1][2]+abs(y-b[0])+abs(x-b[1])
        dp[i][1][3] = dp[i-1][1][3]+[2]
    
   
if dp[w-1][0][2]<=dp[w-1][1][2]:
    print(dp[w-1][0][2])
    for i in dp[w-1][0][3]:
        print(i)
        
else:
    print(dp[w-1][1][2])
    
    for i in dp[w-1][1][3]:
        print(i)
        
    

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

문제

문제

출처

ICPC

이 점화식 어디가 틀렸을까요..?

winnyiee 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말