ABC145 F - Laminate - あっとのTECH LOG

問題原文

問題要旨

$N$ 列のグリッドがあり、各列を下から [H_i] 行塗りつぶしたい。塗りつぶす時は、行方向に好きなだけ塗りつぶせる。
塗りつぶす前に、 $K$ 個まで $H_i$ を好きな値に操作できる時、実際に塗りつぶすのにかかる最小手数はいくつになるか？

考えたこと

$K$ 個まで好きな値に変えられる → $K$ 列まで存在しないことにできるのはわかる
$DP$ っぽい

難しいこと

だからなに？になってしまった
$DP$ の立式ができなかった

考えるべきこと

[tex K] が $N$ 以上なら、明らからに答えは０
$DP$ に必要な要素はなんだろう？
「どこまで見たか？」「いくつ消したか？」は必要そう
「どこまで見たか？」のそれぞれについて、「消す」「消さない」の分岐があるため、「いくつ消したか？」は「いくつ使うと確定したか」のほうがよさそう。
$K = 0$ の場合にはどんな式になるだろう？
上図から、 左隣がいないマスの数 だけコストがかかることことがわかる。
最小の操作回数は、 $(\sum_{i=1}^{n-1} \max(0, H_{i+1} - H_i)) + H_0$ になることがわかる。（一番左に $H_0 = 0$ となるものを追加するのもいい）
ここからまずは $K = 0$ の場合の遷移式を考える。
これは、 $dp[i\rbrack = dp[i - 1\rbrack + \max(0, H[i\rbrack - H[i - 1\rbrack)$ となる。（最初の一つはよしなにやる）
ここから「いくつ使ったのか」を組み込んでいく。
「 $dp[i\rbrack[j\rbrack :=$ $i$ 個目まで見て、 $j$ 個使うとした場合の最小手数」とする。
欲しいのは「最後に使うと決めた列の高さ」。これは、 「確定した列数が１つ少ないところ」 について、それまでに見れる全ての $H_i$ を見れば良い。
つまり遷移式は、 $dp[i\rbrack[j\rbrack = \min_{x=1本目}^{今見ているところの直前}(dp[x\rbrack[j - 1\rbrack + \max(0, H[i\rbrack - H[x\rbrack)$ となる。
肝心の答えは、「 $K$ 列まで無視できる」を考えると、 $\min_{i=1}^{N} {dp[i\rbrack[N - K\rbrack}$ で求められる。

f:id:AT274:20191201175148p:plain

実装

N, K = map(int, input().split())
H = list(map(int, input().split()))

# 全部消せる
if N <= K:
    print(0)
    exit()


dp = [[float('inf')] * (N + 1) for i in range(N + 1)]
dp[0][0] = 0
# 最初に使うとする場合には、その高さ分使う必要がある
for i, h in enumerate(H, start=1):
    dp[i][1] = h


# 2本目以降から考えるようにしている
for i in range(2, N + 1):
    for j in range(2, N + 1):
        for x in range(1, i):
            dp[i][j] = min(dp[i][j], dp[x][j - 1] + max(0, H[i - 1] - H[x - 1]))


for d in dp:
    print(d)
ans = float('inf')
for i in range(N + 1):
    ans = min(ans, dp[i][max(0,  N - K)])

print(ans)

インデックス周りでバグらせそうなので、無理やりいつもの形に持って行ってるけど、 $N$ が増えない $H_0 = 0$ を追加する　のがスマートそう？