문제 링크 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(N^2 lg(D))가 되는데 Judge의 O(N^3)보다 빠를 겁니다.
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(N^2 lg(D))가 되는데 Judge의 O(N^3)보다 빠를 겁니다.
14년 전