【Codeforces】1625C Road Optimization 题解

题目大意

两个城市相聚 $l$ 千米，要从起点城市通过一条路到达目标城市，路上有 $n$ 个限速点（第一个限速点在起点），每个限速点位置在 $d_i$，值为 $b_i$，表示从这个限速点到下个限速点位置，每经过一千米需要花费 $b_i$ 点单位时间。

你可以删掉不超过 $k$ 个限速点，请问删除后到达目标城市的最短时间是多少？

思路

从 A 限速点到达 B 限速点所需时间，与怎么到 A 没有关系，只与还有多少删除机会有关。

进一步讲，到达 A 点肯定是从 A 点前某一个点来的，到达 A 点之后就和它没关系了，所以我们想到了动态规划来解决这个问题。

设 $dp[i][j]$ 表示从起点到达 $i$ 号限速点，并用掉了 $j$ 次删除机会，所能达到的最短时间。

我们从这个点往后走，那么有：

$$dp[i+cnt][j+cnt-1] = \min(dp[i+cnt][j+cnt-1],\ dp[i][j] + (d[i+cnt]-d[i]) \cdot b[i])$$

其中 $j + cnt - 1 \le k$。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int maxN = 505, INF = 0x3f3f3f3f;

int dp[maxN][maxN], n, l, k, b[maxN], d[maxN];

int main()
{
    scanf("%d%d%d", &n, &l, &k);
    for(int i = 0; i < n; ++i)
        scanf("%d", &d[i]);
    for(int i = 0; i < n; ++i)
        scanf("%d", &b[i]);
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0; d[n] = l;
    for(int i = 1; i <= n; ++i)
        dp[i][0] = dp[i - 1][0] + b[i - 1] * (d[i] - d[i - 1]);
    for(int i = 0; i < n; ++i)
        for(int j = 0; j <= k; ++j) 
            for(int pos = i + 1; pos <= n; ++pos)
                dp[pos][j + pos - i - 1] = min(dp[pos][j + pos - i - 1], dp[i][j] + b[i] * (d[pos] - d[i]));
    int ans = INF;
    for(int i = 0; i <= k; ++i)
        ans = min(ans, dp[n][i]);
    printf("%d\n", ans);
    return 0;
}