editorial

---

D

summary:

카드가 위에서부터 $a_0,a_1, \dots, a_{n-1}$ 의 순서대로 쌓여 있는데, $a_0$만 열려 있는 상태이다.

열린 카드에 적힌 수를 $x$라고 할 때, 안 열린 다음 $x$개의 카드를 열거나 $x$점을 획득할 수 있다.

획득할 수 있는 점수의 최댓값을 구하는 문제이다.

solution:

bitset을 이용한 knapsack dp로 해결할 수 있다.

$d_{i,j}=$ $i$번째 카드를 썼을 때, j번째 카드를 열 수 있는지 여부 (실제로는 bitset 하나를 씀)

$d_i=d_{i-1}|(d_{i-1}«a_i)$로 현재 $a_i$로 카드를 연 상태($d_{i-1}«a_i$)와 점수를 획득한 상태($d_{i-1}$)를 갱신시킬 수 있다.

그리고 현재 i에서 $d_{i,i}$가 1이라면 $i$까지 열었고 나머지 카드는 점수를 획득한 상태(열린 카드가 하나도 없는 상태)이므로 $d_{i,i}=0$으로 바꿔주고,

답을 $s_i-(i-1)$로 갱신시킨다.