Cf1625C Road Optimization
题意:
在一条长为 \(1\) 的公路上有 \(n\) 个路标，第 \(i\) 个路标在第 \(d_i\) 米处，限速 \(a_i\) ，意味着在这个路标到下一个路标之间的路段最快速度是 \(a\)；每公里，现在你最多可以移去k个路标（第一个路标除外，因为移掉之后，最开始的一段路就没有限速了），求通过这条路的最短时间是多少。
数据范围:
\(n \le 500\)
思路:
为了方便可以将终点当成一个路牌。
每个路标有两种可能，删掉或者不删掉。然后因为可以删除k个，所以定义 \(f[i][j]:\) 到第 \(i\) 个路牌，已经删除 \(j\) 个路牌需要通过的最短时间。
$f[i][j] = f[i - 1][j - 1] + $ 上一个存在的路牌的速度 $ * (d_i - d_{i - 1})$。
上一个存在的路牌可能是 \(i - 1\) 到 $ i - j$ 之间 ，这也意味着中间删去了若干个路标，所以就以这若干个路标为划分依据。
转移方程:
//前i个路标
for (int i = 2; i <= n + 1; i++)
//最多移走p个路标
for (int p = 0; p <= k; p++)
//从第j个开始，j + 1到i - 1个都不要
for (int j = 1; j < i; j++)
{
int len = i - j - 1;
if (p >= len)
dp[i][p] = min(dp[i][p], dp[j][p - len] + a[j] * (d[i] - d[j]));
}
实现:
#include <stdio.h>
#include <algorithm>
#include<cstring>
using namespace std;
const int N = 510;
int dp[N][N], d[N], a[N];
int main()
{
int n, l, k;
memset(dp,0x3f,sizeof(dp));
scanf("%d%d%d", &n, &l, &k);
for (int i = 1; i <= n; i++)
scanf("%d", &d[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
//将终点看作路标
d[n + 1] = l;
//第一个路标移不走
for (int i = 0; i <= k; i++)
dp[1][i] = 0;
//前i个路标
for (int i = 2; i <= n + 1; i++)
//移走了p个路标
for (int p = 0; p <= k; p++)
//从第j个开始，j + 1到i - 1个都不要
for (int j = 1; j < i; j++)
{
int len = i - j - 1;
if (p >= len)
dp[i][p] = min(dp[i][p], dp[j][p - len] + a[j] * (d[i] - d[j]));
}
printf("%d\n", dp[n + 1][k]);
return 0;
}