kanpurin https://blog.hatena.ne.jp/kanpurin/ かんプリンの学習記録 https://kanpurin.hatenablog.com/ 競技プログラミング 解説 ABC 動的計画法 グラフ 問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 頂点の木と, 各頂点にの値が与えられる. 全ての頂点に対して, 頂点1から頂点までのパスを頂点1から見た数列ととらえて狭義最長増加部分列の長さを求めよ. 思考の流れ ある数列Sが与えられたとき最長増加部分列(LIS)の求め方は, 典型問題である. すべての要素がに初期化された配列Tを用意し, 数列の前の要素から順に見ていき, の要素の中で以上で最も右にある要素を二分探索で見つけ, その値をに書き換える. そのようにしていくと最後にはがLISになっている(を除く). 今回は木であるがその本質は変わらない. 頂点1からDFSを行い… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkanpurin.hatenablog.com%2Fentry%2F2020%2F05%2F02%2F232812" title="ABC165 F - LIS on Tree - かんプリンの学習記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%7B1%5Cle%20N%5Cle%2010%5E%7B5%7D%7D Hatena Blog https://hatena.blog 2020-05-02 23:28:12 rich https://kanpurin.hatenablog.com/entry/2020/05/02/232812 1.0 100%