qnighy
https://blog.hatena.ne.jp/qnighy/
簡潔なQ
https://qnighy.hatenablog.com/
Programming
JOI
概要 番号つきの区間の集合が与えられ、被らない最大個数の区間集合を求める。ただし最大個数の区間集合が複数通りある場合、辞書順で小さいものを選ぶ。 手法 被らない最大個数の区間集合を求める問題は、簡単なDP(区間をendで整列し、ranges[upper_bound(ranges[x].begin)-1].rank+1とranges[x-1].rankのうち大きいほうをとる)という方法で列挙できる。このDPにおける計算の依存関係をグラフに起こすことで、最大値を与える列をグラフから生成できるようになる。このグラフは次のようなものである。 全ての頂点は最大2つの後方リンクをもつ。自身のendの直前(…
190
<iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fqnighy.hatenablog.com%2Fentry%2F20100116%2F1263629683" title="APIO2009 "The Siruseri Convention Centre"解いた - 簡潔なQ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe>
Hatena Blog
https://hatena.blog
2010-01-16 17:14:43
APIO2009 "The Siruseri Convention Centre"解いた
rich
https://qnighy.hatenablog.com/entry/20100116/1263629683
1.0
100%