mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ CodeForces 問題 codeforces.com 解法 集合 A から, D 円以内で交換できる品の集合 B があるなら, 集合 A から集合 B にシフトしていく, というのを貪欲にやっていけば良いです。集合 A と集合 B に同じ品の集合 C がある可能性がありますが, その場合は, A\C, B\C を交換するだけで D 円増やすことが出来るということなので, 問題ありません。コードとしては, まず dp で「集合として値段の合計がいくらになるものがあり得るか」というのを考えて, その後 D 円以下でなるべく増えるように各施工で値段の合計を増やしていきます。 const int MAXN = 55; … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F01%2F20%2F095740" title="Codeforces Round #213 (Div. 1) B. Free Market - mayoko’s diary" 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 2016-01-20 09:57:40 rich https://mayokoex.hatenablog.com/entry/2016/01/20/095740 1.0 100%