BOJ 28033 - Pareidolia

June 3, 2023

$dp[i]$ 를 $i$ 에서 시작하는 모든 substring들의 $B(s)$ 합이라고 하자.

$i$ 에서 시작하는 substring 중에 가장 빠르게 Bessie가 생성되는 마지막 $e$ 의 위치를 $R$ 이라고 할 때,

$dp[i]=(\vert S \vert-R)+dp[R+1]$ 이고 정답은 $\sum_{i=0}^{N-1}dp[i]$ 이다.

그리디하게 가장 빠르게 bessie를 만드는 것이 최적이기 때문이다.

You may also enjoy