Educational DP Contest G (最長経路問題)

atcoder.jp

最長経路問題

• トポロジカルソート
• DP

この二つの組み合わせの問題だった.DPを実行するためにまず初めにトポロジカルソートをした.トポロジカルソートに関しては以前書いたので省く.
トポロジカルソート
今回はトポロジカルソート済みとしてDPを行なっていく.
恒例のDPの定義から

   dp[i] : i 番目までの数字を辿った時の最大の経路数

• 初期条件

   dp[i] = 0; { i = 0 ,1 ,2 ...}

今回は初期条件はあまり重要ではないです。重要なのは次の帰納式

   dp[ to ] = max ( dp[ from ] + 1 , dp[ to ] );

これをトポロジカルソート済みの配列に関してfromのところに順に数字を入れていき実行する.よくわからずなので図形で表してみる トポロジカルソート済みなのでどんどんfromの場所よりも toの場所が右にくることが保証されている.これを用いて今の場所より右の値を更新していくことが可能になる.最終的にdpテーブルが全て埋まったらテーブル内の最大の値を出力すればそれが最長経路となっている。

提出したコード

---

参考にするサイトがあまりなく非常に苦戦しました.最初の提出ではTLEを起こしてしまった。その後配列の中にListを入れる実装に変えることでTLEを回避することができました.