CF1625 C.Road Optimization【线性DP】

题目链接：codeforces 1625C

题解

定义 dp[i][j] 为终点为 ，选中 个点所需要的最少时间。状态转移方程： 其中 为 前 个中的任意节点。方程表示，每次选中的 个点是在 中，而不在 中，不断枚举更新，最后求的的答案是 dp[n+1][k]。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#incldue <cstring>
using namespace std;
const int maxn = 550;
int a[maxn], d[maxn], dp[maxn][maxn];
int main() {
    int n, l, k;
    cin >> n >> l >> k;
    for (int i = 1; i <= n; i++) cin >> d[i];
    d[n+1] = l;
    for (int i = 1; i <= n; i++) cin >> a[i];
	memset(dp, 0x3f, sizeof dp);
    for (int i = 0; i <= k; i++) dp[1][i] = 0;
    for (int i = 2; i <= n+1; i++) {
        for (int j = 0; j <= k; j++) {
            for (int u = 1; u < i; u++) {
                if (j - (i-u-1) < 0) continue;
                dp[i][j] = min(dp[i][j], dp[u][j-(i-u-1)] + a[u] * (d[i] - d[u]));
            }
        }
    }
    cout << dp[n+1][k] << endl;
    return 0;
}