[BOI 2009] Monument

문제: http://www.csc.kth.se/contest/boi/monument.pdf
해법: http://www.csc.kth.se/contest/boi/monument-spoiler.pdf

재미있는 문제다.. BOI 문제들 다 재미있는 듯... 만만한 문제 하나 없다..
O(N^5) 부터 O(N^3) 까지 다양한 방법이 있지만,
O(N^3) 만에 해결해야한다 ^^...

그 방법을 소개하겠다.
Dynamic Programming 을 통해 각 점 (x,y,z)마다 xy 평면에서 점 (x,y,z)를 오른쪽-가장자리로 하는 정사각형의 최대 크기를 precompute(선처리) 해놓을 수 있다. 그 값을 D[x][y][z]라 하자.

그러면 이제 (x,y)의 z축에서 값들을 관찰할거다.
(x,y)를 정하고 한 축(z축) 위를 보는 것이기 때문에 이는 이제 우리가 잘 알고 있는 histogram에서 가장 넓은 직사각형 넓이를 구하는 문제로 바뀐다. (링크)
histogram 문제에서 x축이 이 문제의 z축이 되는것이고, 높이(y축의 값)가 D[x][y][z]의 값이 되는 것이다.

지금 이 작업을 xy 평면에 대해서만 했으므로 yz평면, zx평면에서도 마찬가지 알고리즘을 돌려준다.
(저는 xy평면에서만 하고 100점이 안나와서, 한참을 해맸어요...ㅠ_ㅠ)

monument.cpp