---
title: "Codeforces Round 765 (Div. 2) C(線性DP)"
tags: 題解, DP
---

https://codeforces.com/contest/1625/problem/C

#### 題意

數線上給一些點的座標和通過該點後走一單位的成本。
最多可以刪除 $K$ 個點，問走到終點的最小成本為何。

#### 思路

DP 題，狀態如下：

$dp[i][k]$ 代表刪除了 $k$ 個點後抵達第 $i$ 個點的最小成本。

狀態轉移時考慮從 $i$ 點直接走到 $j$ 點，因此先計算 $i$, $j$ 之間的點，必須刪除的點 ($k2$) 加上 $k$ 後不能大於 $K$。轉移時用 dp[i][k] 更新 $dp[j][k + k2]$，代表刪除了 $k$ 個點抵達 $i$ 後，再刪除 $k2$ 個點從 $i$ 直接抵達 $j$。

答案則是 $dp[N]$ 中的最小值，代表考慮了所有刪除點的可能性後，抵達最後一個點的最小成本。

需注意最後補上 $L$ 這點。

#### Code

def solve():
    N, L, K = map(int, input().split())
    D = list(map(int, input().split()))
    A = list(map(int, input().split()))

    D.append(L)

    dp = [[INF for _ in range(K + 1)] for _ in range(N + 1)]
    dp[0][0] = 0

    for i in range(N):
        v = A[i]
        for k in range(K + 1):
            for j in range(i + 1, N + 1):
                k2 = j - i - 1
                if k + k2 <= K:
                    dp[j][k + k2] = min(dp[j][k + k2], dp[i][k] + (D[j] - D[i]) * v)


    print(min(dp[N]))

if __name__ == "__main__":
    solve()