ナップサック
制約条件:総和=K
AtCoder
多項式・FPS(形式的冪級数)
FPSテク:漸化式の母関数を求める
戻すDP
AtCoder525点
ABC-F
青色diff
DP
ナップサックDP
ナップサック
クエリ:削除
クエリ:挿入
操作
操作:削除
操作:挿入
部分和
各kに対して
「戻す DP」または「FPS」で! 問題へのリンク 問題概要 最初、箱は空である。以下の操作を 回行う。各操作後において、以下の値を答えよ。 箱に入っているボールをいくつか選ぶ方法であって、ボールに書かれた数値の総和が となる方法の個数を 998244353 で…
JOI
JOI本選
JOI難易度6
AOJ
AtCoder
DP
前処理
累積和テク:左右両端からの累積和や累積結果を前処理
部分和
ナップサックDP
累積和
累積和テク:累積和や累積結果を前処理しておく
最大スコア
ナップサック
最適化問題
左右からナップサックした結果を前処理する系! (他の解法もあり) 問題へのリンク editorial 問題概要 (意訳) (実際の問題文は時刻に関する問題) 個の品物がある。それぞれ の番号がついている。番号が の品物は 価値が 重さが となっている。これらを 2 つ…
まさにナップサック問題!!! 問題へのリンク 問題概要 個の饅頭がある。それぞれ 円で売り出そうとしている (全部売るとは限らない)。 饅頭を得るための箱をいくつか購入することにした。箱は 種類あって、 番目の箱は 饅頭を 個まで詰められる 仕入れるの…