cf1625 C. Road Optimization（dp）

题意：

一段长为 (l) 的线段上，给定 (n) 个限速标志。第 (i) 个标志的值为 (a_i)，位置为 (s_i)，表示由此标志走到下一标志需要时间 (a_i(s_{i+1}-s_i))。第一个标志在起点 (0) 处，且必须选择。

现去掉不超过 (k) 个标志，求走完全程的最短时间。

输入均为整数，(nle 500)

思路：

(f[i][j]) 表示走到第 (i) 个标志，已经选了 (j) 个标志且选择第 (i) 个标志的最短时间。

枚举 (i) 的前面最后一个被选的标志 (las)，则 (f[i][j]=min{f[las][j-1]+a_{las}(s_i-s_{las})})，即从 (las) 到 (i) 这段路都用 (a_{las}) 来走。

把终点加上：s[++n]=l，最后答案为必选终点且已选 ([n-k, n]) 个点的最短时间。

const int N = 510;
int n, l, k, s[N], a[N], f[N][N];

signed main()
{
    cin >> n >> l >> k;
    for(int i = 1; i <= n; i++) cin >> s[i];
    for(int i = 1; i <= n; i++) cin >> a[i];

    s[++n] = l;

    memset(f, INF, sizeof f);
    f[1][1] = 0;

    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= i; j++) //至少已选1个
            for(int las = 1; las < i; las++)
                f[i][j] = min(f[i][j], f[las][j-1] + a[las] * (s[i]-s[las]));

    int ans = INF;
    for(int i = n - k; i <= n; i++) ans = min(ans, f[n][i]);
    cout << ans << endl;

    return 0;
}