문제 링크

• http://icpc.me/3136

문제 링크

• http://icpc.me/18477

문제 링크

• http://icpc.me/18702

문제 링크

• http://icpc.me/14636

문제 링크

• http://icpc.me/1787

BOJ에 있는 페트로자보츠크 캠프 문제 출처/에디토리얼 링크 모음 포스팅입니다.
각 Day 별로 문제 출처만 있으면 (o, x), 에디토리얼만 있으면 (x, o), 둘 다 있으면 (o, o)로 표시했습니다.

문제 링크

• http://icpc.me/16191

문제 링크

• 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)$