管理メニュー

競技プログラミング用 知識集積所

F - LCS

最終更新：

sport_programming

- view
管理者のみ編集可

問題


必要知識

ABCのB以下レベルの内容は省略

考え方

最長共通部分列を参照。

解答例


注意点


別解

最長増加部分列を使って解く

実は、最長共通部分列を求めるのに、最長増加部分列のアルゴリズムも使える。

  • sの最初の文字について、tにある同じ文字の位置を後ろから順に記録
  • sの次の文字について、tにある同じ文字の位置を後ろから順に記録
  • （中略）
  • sの最後の文字について、tにある同じ文字の位置を後ろから順に記録
を全部並べた数列を作る。

その数列の最長増加部分列を求め、tからその位置の文字を拾っていけば解答となる。

タグ：

最長共通部分列 動的計画法 バックトレース
「F - LCS」をウィキ内検索
「最長共通部分列」関連ページ
人気タグ「set」関連ページ
もっと見る
人気記事ランキング
  1. ABC 401-500/ABC410C - Rotatable Array
  2. ABC 401-500/ABC415C - Mixture
  3. ABC 401-500/ABC404B - Grid Rotation
  4. 内容別リスト/変数とデータ構造/string型
  5. 内容別リスト/基本/cout
  6. 内容別リスト/基本
  7. レベル別リスト/C問題レベル
  8. 内容別リスト
  9. ABC 401-500/ABC401E - Reachable Set
  10. ABC 401-500/ABC406A - Not Acceptable
もっと見る
最近更新されたページ
もっと見る
ウィキ募集バナー