문제 링크

• http://icpc.me/14510

문제 링크

• http://icpc.me/18263

서론

Monotone Queue Optimization은 점화식이 아래 조건을 만족할 때 사용할 수 있습니다.

• 점화식 꼴 : $\displaystyle D(i) = \min_{1 ≤ j < i}{D(j) + C(j, i)}$
• 조건 : $i < j$인 임의의 $i, j$에 대해 다음을 만족하는 지점 $cross(i, j)$가 존재
  • $cross(i, j) > k$이면 $D(i) + C(i, k) < D(j) + C(j, k)$
  • $cross(i, j) ≤ k$이면 $D(i) + C(i, k) > D(j) + C(j, k)$

서론

DP 최적화를 공부하다보면 monge array라는 것이 많이 보이지만, 정작 monge array에 대한 설명은 많이 없습니다.
이 글에서는 monge array의 정의와 몇 가지 성질의 증명을 다룹니다.

문제 링크

• http://icpc.me/17439

PS 실력을 키우기 위해 3월 13일부터 4월 10일까지 총 4주동안 적절한 문제들을 골라서 연습했습니다.
이 글에서는 연습에서 사용한 문제들과 문제에 관한 후기와 몇 가지 스포를 포함하고 있으니 주의 바랍니다.

문제 링크

• http://icpc.me/18596

문제 링크

• http://icpc.me/13145

문제 링크

• http://icpc.me/3319

서론

이 글은 독자가 MCMF와 Dinic’s Algorithm을 알고 있다고 간주하고 설명합니다.
Min Cost Max Flow(MCMF) 문제를 해결하는 방법은 잘 알려져 있습니다.
이 글에서는 이 MCMF를 구하는 알고리즘에서 수행하는 몇 가지 비효율적인 작업 최적화하는 방법을 다룹니다.