F - Knapsack for All SubsetsABC実質初全完を祝って解説記事。 概要 長さNの数列Aが与えられる。また、{1, 2, ..., N}が含まれる集合Xを考える。Xの空でない部分集合Tについて、次のf(T)を定める。 f(T) := Tの空でない部分集合を{t_1, t_2, ..., t_i}とす…

atcoder.jp 概要 長さNの数列A[]が与えられる。次のようにf(l, r)を定める。 l さて、1 制約： 1

arc073.contest.atcoder.jp ナップサック問題に制約、 Wがばかでかいので当然普通のdpではMLEする。 ここでＮが小さいときに注目、Ｎが小さいときにうまくいくのは全探索、全列挙的な手法となる。 100では全列挙は厳しいけど、ここで、重さは４通りしかない…