問題はこちら
問題概要
正整数列に対して次の操作を回以上行う.- から連続部分列を選び,削除する.
に対し,の要素の総和をちょうどにするために必要な操作回数の最小値を求めよ.
解説
操作も制約も明らかにDPの気配がします。そうすると自然に以下のDPを思い付きます。
までで、ちょうどにするために必要な操作回数の最小値
求める値はです。
- 左端を、右端をとする連続部分列に対して操作を行う場合、
- を含む連続部分列に対して操作を行わない場合、
からの遷移があり、これらの最小値がとなります。
しかし、このままだと時間計算量となり間に合いません。
ここで、各遷移がどのようになってるのかをDPテーブルを見ながら考えてみましょう。
★の値を求めるためには赤枠の値の最小値と青枠の値を求める必要があります。
赤枠の値を各★毎に求めているとの計算量がかかってしまいますが、のときの赤枠との赤枠はほとんど同じであることを利用することで計算量を減らすことができます。
具体的には以下のような順番で赤枠の最小値を持ちながら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])