alien

Slope Trick처럼 DP의 Convexity를 활용해 최적화하는 트릭이다. 정확히K개 조건을 풀어버릴 때 사용한다. 최대K개라고 적혀있지만 볼록성때문에 K개 전부 사용하는게 최적이다. 대충 최대j개 고를 수 있는 dp의 경우 f(i,j)=min{k<i}{f(k,j-1)+cost(i,k)} 이런 형태가 나오는데, cost(i,k)가 j에 독립적이면서 최종적으로 j개 더해지는것을 식으로 표현해서 lagrange relaxation form으로 표현해 최적화하는것 같다. 이 lagrange relaxation이 등호제약조건 최적화문제에서 duality gap = 0이라고 알고있다. 더 자세한 이론적 내용은 잘 모르겠고 지금까지 적은 내용도 헛소리한걸수도 있으니 더 궁금하면 https://codeforces.com/blog/entry/98334 이 글을 읽어보자.

relaxed form에서는 convex한 dp식이 최적화 가능한형태로 종종 등장하며, 구현은 lambda값 범위를 구간개수역추적을 통해 이분탐색하거나 위에 링크한 글의 dual에서의 삼분탐색 두가지 방법이 있다. 삼분탐색은 역추적할 필요가 없어 구현이 간단하지만, 듀얼최적화가 종종 그렇듯이 실제 답을 복원하는게 어렵거나 불가능해보인다. 이분탐색은 역추적이 필요해 구현이 좀 더 복잡한데 대신 답 복원이 가능하다.