79brue의 PS 블로그

슬슬 문제를 푸는 것이 귀찮아지고 있다. D4-D3권에서 남은 문제들을 푸는 것이 쉽지 않아 보인다. 그래도 아직 문제가 꽤 남았으니 이 부분에서 조금 더 풀어 볼 생각이다. 뭔가 문제를 푼 사람이 많을수록 더 풀기 쉬울 것 같으니, 이번에는 푼 사람 순서대로 정렬을 해 봤다. 남은 문제: 60 → 55문제BOJ 20558. 쿼리와 수열$K_i$의 합을 $K$라고 쓰자. 다음과 같이 상태가 $O(NK)$개인 DP를 만드는 것은 쉽다.$DP[i][j][v]$: 구간 $(i, j)$에서 최댓값이 $v$인 경우 답의 최댓값이때 $(i, v)$ 또는 $(j, v)$의 쌍이 $K$개 이하이므로 전체 $(i, j, k)$의 쌍이 $O(NK)$개 이하가 된다. 다만 저렇게 하면 transition의 가짓수가 $K$개..