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]) * 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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/02/04/codeforces-1625-c/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！