다다스의 부분수열

먼저 하나의 수열 $B=(b_1,b_2,\ldots,b_m)$에 대해 $g(B)$를 구하는 일반적인 DP를 생각하자.

$$dp_i=\max(dp_{i-1},dp_{i-2}+b_i)$$

로 둘 수 있다. 여기서 $dp_i$는 앞 $i$개의 원소만 고려했을 때의 답이다.

이제

$$d_i=dp_i-dp_{i-1}$$

라고 정의하자. 그러면

$$\begin{aligned} d_i &=dp_i-dp_{i-1}\\ &=\max(dp_{i-1},dp_{i-2}+b_i)-dp_{i-1}\\ &=\max(0,b_i-(dp_{i-1}-dp_{i-2}))\\ &=\max(0,b_i-d_{i-1}) \end{aligned}$$

이다.

또한

$$dp_m=d_1+d_2+\cdots+d_m$$

이다. 따라서 모든 부분수열에 대한 $g(B)$의 합은, 모든 부분수열에서 각 원소가 추가될 때 생기는 $d$값의 합과 같다.

중요한 점은 $1 \le A_i \le 10$이므로 모든 $d_i$도 $0$ 이상 $10$ 이하라는 것이다.

$cnt[j]$를 현재까지 본 원소들로 만들 수 있는 비어 있지 않은 부분수열 중, 마지막 $d$값이 $j$인 부분수열의 개수라고 하자.

새 원소 $x=A_i$를 처리할 때 새로 생기는 부분수열은 두 종류이다.

• $x$ 하나만 고른 부분수열: 이때 마지막 $d$값은 $x$이다.
• 기존 부분수열 뒤에 $x$를 붙인 부분수열: 기존 마지막 $d$값이 $j$라면 새 마지막 $d$값은 $\max(0,x-j)$이다.

새로 생긴 모든 부분수열의 마지막 $d$값은 전체 답에 한 번씩 더해져야 한다. 그러므로 새로 만든 상태를 $add$에 모으면서

$$ans \mathrel{+}= add[d]\cdot d$$

를 해 주면 된다.

그 후 $cnt[d]$에 $add[d]$를 더하면, 다음 원소를 처리할 때 사용할 수 있다.

상태 수는 $0,1,\ldots,10$ 총 $11$개뿐이므로 각 원소마다 $O(11)$에 처리할 수 있다.

시간 복잡도는 $O(11N)$, 메모리 복잡도는 $O(11)$이다.