betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ AOJ プログラミング 競技プログラミング お題箱より。 Aizu Online Judge 解法 重み の負辺を足してできるだけ重み合計が大きい（ に近い）負閉路を作りたいので、与えられたDAGについて「1本以上の辺で構成されるパスであって、重み合計が 未満であるもののうち一番大きいものの重み」が分かれば良いです。 ここで であること、さらに元々のDAGにある辺の重みは非負であることに注目します。これらの条件から、最終的に見つけるパスも、その一部となるパスも、重みが 以下のものだけを考えれば良いことが分かります。 よって以下のようなDPテーブルを構成し、 の範囲で計算していけば良いです。 ：1本以上の辺で構成され、頂点 で終わるパスで… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2020%2F08%2F09%2F150101" title="University of Aizu Programming Contest 2014 (AOJ 1548) Yu-kun Likes a Directed Graph - ARMERIA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/106916089/1592411661884548 Hatena Blog https://hatena.blog 2020-08-09 15:01:01 rich https://betrue12.hateblo.jp/entry/2020/08/09/150101 1.0 100%