管理メニュー

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

F - LCS

最終更新：

sport_programming

- view
管理者のみ編集可

問題


必要知識

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

考え方

最長共通部分列を参照。

解答例


注意点


別解

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

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

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

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

タグ：

最長共通部分列 動的計画法 バックトレース
「F - LCS」をウィキ内検索
「動的計画法」関連ページ
人気記事ランキング
  1. DPまとめコンテスト
  2. DPまとめコンテスト/F - LCS
  3. 内容別リスト/データ探索系/最長共通部分列
  4. 内容別リスト/高速化系/バックトレース
  5. DPまとめコンテスト/K - Stones
  6. 内容別リスト/データ探索系/最長増加部分列
  7. 内容別リスト/高速化系
  8. レベル別リスト/E問題レベル
  9. 内容別リスト/高速化系/動的計画法
  10. レベル別リスト/C問題レベル
もっと見る
最近更新されたページ
もっと見る
ウィキ募集バナー