挿入型動的計画法の解説
概念
挿入型動的計画法（DP）とは、特定の順列に基づいてDPを行う問題で、計算量は一般的にO(n2)からO(n3)の範囲内です。この種の問題では、順列内の昇順や降順の変化点が答えに大きな影響を与えます。
基本的なアプローチは以下の通りです：
数値を小さい順に挿入し、その段階で状態設計を行います。これにより、既に挿入された数値は現在の数値より小さく ...
8月1日 16:29 投稿
鋳造炉の容量制約下における最大耐久性の動的計画法
問題定義
特殊な錬成炉を用いて伝説の武器を鍛造する際、計 N 種類の素材を準備します。各素材 i には固有の強度パラメータ A[i] が割り当てられています。錬成規則により、素材は番号順（1 から N まで）に厳密に投入しなければなりません。
炉の容量は最大 W 個の素材までです。ここで重要な操作制限として、新しい素材を投入する直前 に限り、炉内に保管されている素材 ...
7月28日 19:24 投稿