동적 프로그래밍 최적화, 볼록 선체

Question

컨테스트에서 문제가 발생했습니다. 나는 이미 동적 프로그래밍과 그 복잡성으로이 문제를 해결했다. O(n^2). 그러나 나는 더 효율적인 방법을 찾고있다. 나는 동적 프로그래밍이 볼록 선체로 최적화 될 수 있음을 이미 보았습니다. 제안 할 것이 있습니까. 덕분에 조언.

Answer 1

복잡도가 다른 여러 알고리즘이 convex hull algorithms에 나와 있습니다.

Answer 2

당신은 아마 동적 프로그래밍에 대한 볼록 선체 트릭을 언급하고 있습니다 : http://wcipeg.com/wiki/Convex_hull_trick