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$에 채우면 된다.
정확히 검증을 안하고 풀어서 자세한 설명은 불가능하다.
Comments