https://kanpurin.hatenablog.com/entry/2022/12/13/134224

問題はこちら

問題概要

正整数列 ${A=(a_1,a_2,\dots,a_N)}$ に対して次の操作を ${0}$ 回以上行う．

${A}$ から連続部分列を選び，削除する．

${x=1,2,…,M}$ に対し， ${A}$ の要素の総和をちょうど ${x}$ にするために必要な操作回数の最小値を求めよ．

${1\leq N,M,a_i\leq 3000}$

解説

操作も制約も明らかにDPの気配がします。

そうすると自然に以下のDPを思い付きます。

${dp[i][j]:=a_i}$ までで、ちょうど ${j}$ にするために必要な操作回数の最小値
求める値は ${dp[N][x]}$ です。

左端を ${a_k}$ 、右端を ${a_i}$ とする連続部分列に対して操作を行う場合、 ${dp[k-1][j]+1}$
${a_i}$ を含む連続部分列に対して操作を行わない場合、 ${dp[i-1][j-a_i]}$

からの遷移があり、これらの最小値 ${\min(\underset{1\leq k\leq i}{\min}(dp[k-1][j]+1),dp[i-1][j-a_i])}$ が ${dp[i][j]}$ となります。

しかし、このままだと時間計算量 ${O(N^2M)}$ となり間に合いません。

ここで、各遷移がどのようになってるのかをDPテーブルを見ながら考えてみましょう。

★の値を求めるためには赤枠の値の最小値と青枠の値を求める必要があります。

赤枠の値を各★毎に求めていると ${O(N)}$ の計算量がかかってしまいますが、 ${dp[i][j]}$ のときの赤枠と ${dp[i-1][j]}$ の赤枠はほとんど同じであることを利用することで計算量を減らすことができます。

具体的には以下のような順番で赤枠の最小値を持ちながらDPテーブルを埋めていけばよいです。

提出プログラム

N,M = map(int,input().split())
a = list(map(int,input().split()))
INF = 10**10
 
dp = [[INF]*(M+1) for _ in range(N+1)]
 
dp[0][0] = 0
 
for j in range(M+1):
    premin = 0 if j == 0 else INF
    for i in range(N):
        if j >= a[i]: dp[i+1][j] = dp[i][j-a[i]]
        dp[i+1][j] = min(dp[i+1][j],premin+1)
        premin = min(premin,dp[i+1][j])
 
for x in range(1,M+1):
    if dp[N][x] == INF:
        print(-1)
    else:
        print(dp[N][x])

感想

基本的なDP高速化問題でした。