BOJ 28033 - Pareidolia
$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를 만드는 것이 최적이기 때문이다.
Comments