BOJ 14706 - 구간 합 최대

BOJ 14706 - 구간 합 최대

조건들을 $(L_i, S_i)$ 에 대해 정렬하고 $i < j$ 라면 $L_i < L_j, ~ S_i < S_j$ 가 되도록만 조건들을 남겨주자.

길이가 더 길거나 같은데 $S_i$ 가 더 작다면 그것이 더 강력한 조건이기 때문에 이전 조건들을 무시할 수 있기 때문이다.

그러면 문제가 단순해진다.

$O(NM)$ 에 직접 가장 최적이 되는 배열을 채워줄 수 있다.

젤 첫번째엔 $S_0$ 을 채워주고 $L_0-1$ 개의 $0$ 을 채워준다.

이제 현재 자리가 $x$ 이고 $j$ 번째 조건을 보고 있다고 할 때,

가능한 것중 가장 큰 값을 정하기 위해 모든 조건들을 순회하며 $S_j-\sum_{i=x-L_j+1}^{x-1} a_i$ 가 작은 수를 골라주고 그것을 $x$에 채우면 된다.

정확히 검증을 안하고 풀어서 자세한 설명은 불가능하다.