drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder DP シーケンシャルDP 部分和 数え上げ問題 データ構造テク：前処理 数学(整数問題) けんちょん本演習問題 EDPCとTDPC NoviSteps2Q 部分和問題とほとんど一緒なのだけど、意外と詰まるかもしれない。 問題へのリンク 問題概要 個の正の整数 の中からいくつか選んで総和をとる。作ることのできる整数が何通りあるか求めよ。 制約 考えたこと この問題とよく似た部分和問題とは次のような問題である。 個の正の整数 の中からいくつか選んで総和をとった値を にできるかどうかを判定せよ この問題に対しては次のような配列 dp を定義することで解くことができる。 ← 個の整数のうち最初の 個の整数の中からいくつか選んだ総和を にできるかどうか 遷移はこんな感じにできる ( の範囲に注意)。 dp[i][j] = true のとき dp[i+1][… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F12%2F21%2F153600" title="TDPC (Typical DP Contest) A - コンテスト (2Q) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-12-21 15:36:00 rich https://drken1215.hatenablog.com/entry/2020/12/21/153600 1.0 100%