ABC 104 D We Love ABC

DPの問題

atcoder.jp

これは状態を列挙することと, どのように状態が遷移するかを見ることが必要となる.

今回の場合は文字の長さを i 番目まで見た時に状態がいくつあるか.

1. ABCどれも使わない
2. Aを使う場合
3. ABまで使う場合
4. ABCまで使い完成している場合

以上の4つも状態が考えられる.
そのため4つの状態のdoテーブルを用意して実装する.
文字のi番目を監視して , A B C ? のいずれかなのでこれらを場合分けして状態を更新していくとdpが完成する