全ての開発案を実行するかどうかを全通り試す \(\mathrm{O}(2^N N K)\) 解法は間に合いません。そこで、\(P\) を超えたステータスは \(P\) で打ち切ってもよいため途中でのステータスの種類は実質 \(\mathrm{O}((P+1)^K)\) 通りしかないことに注目します。すると、次のような動的計画法が考えられます。

• \(\mathrm{dp}[i][a] = i\) 個目の開発案までを実行するかどうか決めて、ステータスの配列が \(a=(a_1,a_2,\dots,a_K)\) になるようなコストの総和の最小値(達成不可能なときは \(\infty\) とする。)

\(a\) の要素のうち \(P\) を超えたものは全て \(P\) にすることで、状態数を \(\mathrm{O}(N(P+1)^K)\) 個に抑えられます。遷移は、\(i+1\) 個目の開発案を実行するかしないかの \(2\) 通りでそれぞれ \(\mathrm{O}(K)\) で遷移できるため、この解法の計算量は \(\mathrm{O}(NK(P+1)^K)\) となります。これは十分高速です。

実装においては、\(a\) を \(K\) 桁の \(P+1\) 進数の整数として扱うことで実装が簡単になります。もしくは、C++ などの高速な言語だと \(a\) を vector で管理して、dp に map を使うなどをしても良いです。