CF1625C - Road Optimization

Problem : Codeforces Round #765 (Div. 2) - C. Road Optimization

let $dp[i][j]$ be the minimum time to move up to sign $i$ and $j$ signs where $j$ is $[1 .. i - 1]$ are removed.

We can iterate all the stops, try all $k$ on each possible position $p$ where $p$ is the previous stops $1 .. p - 1$. For example, if we need to move from stop $p$ to sign $i$ directly, then all signs between these two stops has to be removed. The total time is simply $(d[i] - d[p]) * a[p]$. And we need to add the previous part $dp[p][j - (i - p - 1)]$. If we remove all signs from stop $p$ to $i$, so basically it is $i - p - 1$. There is a constraint that we cannot remove no more than $k$ signs, so we check if previous $j$ signs that have been removed is greater than $0$ or not. If so, then we can update take the minimum of $dp[i][j]$ and $dp[p][j - (i - p - 1)]$.

void solve() {
    long long n, l, k; 
    cin >> n >> l >> k;
    vector<long long> d, a;
    for (int i = 0; i < n; i++) cin >> d[i];
    for (int i = 0; i < n; i++) cin >> a[i];
    d.push_back(l);
    vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 1e18));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            for (int p = i - 1; p >= 0; p--) {
                int old_j = j - (i - p - 1);
                if (old_j >= 0) {
                    dp[i][j] = min(dp[i][j], dp[p][old_j] + (d[i] - d[p]) * a[p]);
                }
            }
        }
    }
    cout << *min_element(dp.back().begin(), dp.back().end()) << endl;
}