drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ Codeforces CodeforcesDIV1-B CodeforcesR1800 LCS DP 文字列 連続部分列を扱う問題 f(i,j)をiとjとに分離する 考察：操作・条件・目的関数を言い換える LCS型DP 結構悩んだ！！！ 問題へのリンク 問題概要 長さ の文字列 と、長さ の文字列 が与えられる。 の連続する部分文字列 と、 の連続する部分文字列 をとったとき、 とする。 の考えられる最大値を求めよ。 制約 考えたこと 単純にそれぞれの部分文字列を探索したのでは の計算量となってしまう。 ここで、LCS を求めるときの DP を思い出しながら、スコアを少し言い換えてみることにする。 として 1 文字を付け加えたとき、スコアは 1 減少する として 1 文字を付け加えたとき、スコアは 1 減少する から 1 文字、 から 1 文字付け加えたとき、それらが等しいならば、スコアは 2 増加する この… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F11%2F30%2F043120" title="Codeforces Round #683 (Div. 1) B. Catching Cheaters (R1800) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-11-30 04:31:20 rich https://drken1215.hatenablog.com/entry/2020/11/30/043120 1.0 100%