문제 링크 http://2008.nwerc.eu/problems/nwerc08-problemset.pdf
Judge의 solution http://2008.nwerc.eu/problems/nwerc08-solutions.pdf
제가 소개할 풀이는 Judge 답만큼 깔끔한 것도 아니고 좀 더럽습니다. 그냥 Judge의 것과 다른 solution이 있다는 정도로 위안을...
일단 용어 정의부터.
cost[i,j] : 0..i 사이의 stack들을 조절하였을 때 Hi = j를 만족하는 최소비용
mincost[i] : min(cost[i,-inf...inf])
minrange[i] : cost[i,...]에 대하여 cost[i,j] = mincost[i]를 만족하는 j의 집합. 하나의 폐구간으로 표현가능하다.
계산하는 방법은
cost[i,j] : j가 minrange[i-1]과 d 이하만큼 가까우면 mincost[i-1] + abs(j - Hi), 그렇지 않으면 j에서 minrange[i-1] 방향으로 d만큼 이동한 지점 k에 대해 cost[i-1,k] + abs(j - Hi)
mincost[i] = minrange[i-1]에 d 이하만큼 가까우면서 Hi 와 가장 가까운 점 j에 대해 cost[i,j]를 계산
minrange[i] : j,j+1,j+2,... 혹은 j,j-1,j-2,... 중 하나인데 이건 그냥 binary search로 검색한다.
cost[i,j]의 계산량을 O(N)이고, mincost의 계산량은 O(1), binary search의 경우 값의 전체 범위 D에 대해 O(N lg(D)), 결국 모든 N에 대해 계산량은 O(N2 lg(D))가 되는데 Judge의 O(N3)보다 빠를 겁니다.
Neon
문제 링크
http://2008.nwerc.eu/problems/nwerc08-problemset.pdf
Judge의 solution
http://2008.nwerc.eu/problems/nwerc08-solutions.pdf
제가 소개할 풀이는 Judge 답만큼 깔끔한 것도 아니고 좀 더럽습니다. 그냥 Judge의 것과 다른 solution이 있다는 정도로 위안을...
일단 용어 정의부터.
cost[i,j] : 0..i 사이의 stack들을 조절하였을 때 Hi = j를 만족하는 최소비용
mincost[i] : min(cost[i,-inf...inf])
minrange[i] : cost[i,...]에 대하여 cost[i,j] = mincost[i]를 만족하는 j의 집합. 하나의 폐구간으로 표현가능하다.
계산하는 방법은
cost[i,j] : j가 minrange[i-1]과 d 이하만큼 가까우면 mincost[i-1] + abs(j - Hi), 그렇지 않으면 j에서 minrange[i-1] 방향으로 d만큼 이동한 지점 k에 대해 cost[i-1,k] + abs(j - Hi)
mincost[i] = minrange[i-1]에 d 이하만큼 가까우면서 Hi 와 가장 가까운 점 j에 대해 cost[i,j]를 계산
minrange[i] : j,j+1,j+2,... 혹은 j,j-1,j-2,... 중 하나인데 이건 그냥 binary search로 검색한다.
cost[i,j]의 계산량을 O(N)이고, mincost의 계산량은 O(1), binary search의 경우 값의 전체 범위 D에 대해 O(N lg(D)), 결국 모든 N에 대해 계산량은 O(N2 lg(D))가 되는데 Judge의 O(N3)보다 빠를 겁니다.
16년 전