totaltech365 https://blog.hatena.ne.jp/totaltech365/ TotalTech https://totaltech365.hatenablog.com/ 競技プログラミング AtCoder 「条件を手で計算してみる大切さ」を教えてくれる問題です。 ソートしてからナップサックDPで解けます。 問題 種類の活動の中から つ以上を選び、好きな順序で行なう。 最初の体力は であり、活動 を行うと、得点 を得た後、体力が 減少する。 得られる得点の和の最大値を求めよ。 制約 考察 活動を行った時に得られる得点が「その時点の体力」に依存するので、そのままナップサックDPは使えません。 しかし、活動の順序を全検索（ 通り）することは、時間的に不可能です。 ここで、活動 → 活動 を行った場合と、活動 → 活動 を行った場合の、それぞれ得られる得点を計算してみます。 体力の減少は、どちらも同じ … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftotaltech365.hatenablog.com%2Fentry%2Fpast202104_n" title="AtCoder 第六回 アルゴリズム実技検定 (PAST): N - 活動 - TotalTech" 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 2021-07-06 07:37:53 rich https://totaltech365.hatenablog.com/entry/past202104_n 1.0 100%