トポロジカルソートを書いてみたので記録しておく. ToplogocalSortとは. edgeをソートする方法の一種である。並び替えをします.ソートされた後の配列をみた時に配列の左から右向きのpathは存在するが右から左むきのpathは存在しないようにするということです…

atcoder.jp LCS(Longest Common Subsequence)最長経路問題です。 問題 文字列s , tが与えられた時に共通部分列で最長の物を求める. 最初全探索するのかと思ったが明らかに実行時間が間に合わない。それならばDPだろう.今回のDPの定義としては lcs[i][j] : 文…

atcoder.jp ナップザック問題のversion2.価値に制限がある場合.重さに制限がある場合と解き方が異なります. 提出 DPで解く ナップザック問題といえばおなじみのDPですが今回はDPの定義が難しい.いつもの重さに制限がある場合は dp[i][j] : i 個まで見た時の…