CF1625C - Road Optimization

Problem : [Codeforces Round #765 (Div. 2) - C. Road Optimization](https://codeforces.com/contest/1625/problem/C)  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)]$. ```cpp 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; } ```