2017-08-26から1日間の記事一覧

Typical DP Contest R - グラフ

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_graph 解法 どう考えても閉路は一つにまとめたいな~という気持ちになるので,とりあえずSCCしたあとのDAGの上で解くことを考えます. 一番端っこから引いていくのが当然良いので,トポロジカルソートして…

Typical DP Contest P - うなぎ

問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_eel 解法 木の上でのDPなので,やはり根を適当に決めたあとのDFS木上で,部分木の結果を統合していくのが鉄則となります.根として適当に頂点 0 を選んで,そのDFS木上で考えます. 以下のような dp を考…