E - Break-The-Brick !

この問題では動的計画法を問います。

ほぼ「いくつか選んだ整数の和を $S$ にすることができるか？」という部分和問題ですが、このままでは正しい解答は得られません。
ではどうすればよいのでしょうか？

操作を見直してみます。

• 積み木を落とす操作は、現時点で重なっている積み木に書かれた整数の総和から落とした積み木に書かれた整数を引く
• 積み木を残す操作は、総和には何の変化もない

こうして見てみると、本問題は次のように言い換えられます。

「残っている積み木に書かれた整数の総和を $S$ にすることができるか？」
$\Leftrightarrow$ 「落とした積み木に書かれた整数の総和を $\displaystyle\sum^{N}_{i=1} A_i-S$ にすることができるか？」

今回は落とす積み木の候補を決めるのでこの問題に帰着できると実装ができます。
したがって最初に書かれた問題の $S$ を $T=\displaystyle\sum^{N}_{i=1} A_i-S$ としてこの部分和問題を解くことで正解することができます。これは動的計画法(DP)を用いて実装できます。

$dp[i][j]\ :=$ 上から $i$ 個目の積み木を落として、落とした積み木の総和を $j$ にするための落とす積み木の個数の最小値

とします。初期値(操作前)は $dp[0][0]=0,dp[i][j]=\infty \ (0\le i\le N-1,0\le j\le T,i\neq 0$ または $j\neq 0)$ です。ここでは 0-indexed で考えます。
遷移は $i=0,1,...N-1$ また $j=0,1,...T$ に対して以下のようになります※。

• $dp[i+1][j] = \min(dp[i+1][j],dp[i][j])\ (j < A_i)$
• $dp[i+1][j] = \min(dp[i+1][j],dp[i][j-A[i]]+1)\ ( j \geq A_i )$

答えは $dp[N][T]$ です。
ただし $dp[N][T]=\infty$ の場合、これは条件を満たす操作方法が存在しないことを表すので、答えは -1 です。

以上から $O(NT)=O(N(\displaystyle\sum^{N}_{i=1} A_i-S))$ で実装することができます。以下は解答例(C++,Python)です。

※なぜこのような遷移になるかは、自分で調べてみてください。ここでは省略します。