BOJ 18858 - 훈련소로 가는 날

BOJ 18858 - 훈련소로 가는 날

구간합 배열을 잘 쓰면 $O(NM)$ 에도 풀 수 있다.

단순하게는 $O(NM^2)$ 으로 푸는 방법이고, 두 방법은 다르지 않다.

$dp[i][j][big]$ 를 $i$번째 수까지 이전 수가 $j$이고 전전수보다 이전수가 큰지 여부가 $big$일 때 경우의 수로 두면 된다.

1등잼