perogram

E. Subsequences (easy version)

Quiz

https://codeforces.com/contest/1183/problem/E

  • string sが与えられる
  • K個の部分文字列を作るのに必要な最低コストを求めよ
  • 部分文字列tを作るコストは、sから取り除いた文字数である

AC Code

https://codeforces.com/contest/1183/submission/56179608

考察

  • 部分文字列を各長さでいくつ作れるかが分かればいい
  • それってDPでできそう
    • 実際にできるのだが、分からなくて終了

想定解

  • しかし今回の設定ではN, Kが100までと緩い
  • よって想定解はBFSによる全探索

f:id:peroon:20190628070058j:plain