Sum of Adjacent Minimums

따라서 이러한 꼴의 해만 생각한다면 얻을 수 있는 최댓값은 $XM$이다.

그중 하나가 $[l,r]$이라면, 이 구간에서 서로 이웃하게 남아 있는 인덱스 쌍은 $r-l$개이다. $M$의 정의에 의해 $(r-l)\leq M(C_l+C_{l+1}+\cdots+C_r)$가 성립한다.

모든 연속 구간에 대해 더하면, 높이 $t$에서 동시에 남아 있는 이웃한 인덱스 쌍의 수는 $M\displaystyle\sum_{\substack{1\leq i\leq N\\R_i\geq t}} C_i$ 이하이다.

높이 $t$에서 동시에 남아 있는 이웃한 인덱스 쌍의 수를 $K(t)$라고 하자. 각 $(i,i+1)$은 $0\leq t\leq\min(R_i,R_{i+1})$인 동안 정확히 하나씩 세어지므로, 목적함수의 값은 $\int_0^\infty K(t)\,dt$이다. 따라서 위 부등식을 $t\geq 0$에 대해 적분하면

를 얻는다.

이제 $M$을 만드는 구간 $[l,r]$을 하나 고르자. $l\leq i\leq r$인 모든 $i$에 대해

로 두고, 나머지 $R_i$를 $0$으로 둔다. 그러면 조건을 만족하며 목적함수의 값은 $XM$이다.

따라서 $XM$이 정확한 최댓값이다.