NCPC 2007
http://ncpc.idi.ntnu.no/ncpc2007/
- G번
데이터를 높이순으로 감소시키고,(높이가 같다면 넓이가 큰것으로) 정렬시킨다.
그다음 1번부터 순서대로 돌면서 이미 돈 좌표에서 마지막에 연결시킨다(최대한 넓이가 작은것으로, 같다 면 넓은것을 먼저 선택). 마지막의 저장점은 은 벡터로 하면 되고 정렬시킬 필요는 없다.(자동적으로 정렬 만약 새로은 좌표가 저장되면 해당 인덱스를 새로운 좌표로 수정한다. 그리고 연결되지 않으면 해당 벡터에 추가 시키면 된다. 다돈후 저장점 벡터의 길이를 출력하면 된다.
이렇게 되는 이유가 해답에 나와 있는데, 설명이 약간 어렵게 된거 같다.
모순으로 증명한다. 최적의 해가 위의 방법과 다른 선택을 하는 가장 작은 순서를 d라고 하고, 위의 방법으로 선택한 것을 dlow라 하고, 최적의 해가 선택하는 것을 dopt라고 하자. 여기서 우리가 알수 있는것은 넓이는 dlow <= dpot이다.
여기서 최적의 해에서 dlow에 연결되는 좌표가 있을수도 있고 없을수도 있다. 없다면 d를 dlow에 연결시킨다.(연결된후의 큰것들은 신경쓰지 않아도 된다.) 만약 있다면(dwrong이라 하자) dwrong과 dopt를d와 dlow를 연결시키자.(dwrong의 넓이는 dlow보다 작으므로 dopt보다 작다.) 이렇게 하면 결국 우리의 선택은 최적해와 같게 된다.
또다른 방법
http://en.wikipedia.org/wiki/Dilworth%27s_theorem
- I (moogle)
다이나믹 문제다.
최초 생각은 d[시작점][끝점][저장할개수]로 다이나믹으로 풀었다.
저장개수 -> 시작점 -> 끝점 -> d[시작][중간][i] + d[중간][끝][저장개수 - i +1]중 가장 작은것 구했는데(O(n^4)), 해설을 보니 굳이 이렇게 할 필요가 없다. d[0][중간][저장개수-1] + d[중간][끝][2]중 가장 작은걸로 구하면 된다(O(n^3))
거의 맞는데 몇개의 테스트 케이스에 대해서 조금의 오차가 생기는데 왜그런지..ㅡㅜ
(이유는 모두다 저장하는 경우를 0으로 초기화 하지 않아서이다..ㅡㅜ)
I.cpp
