CF1625C-Road Optimization
题目大意：一条路可以视为一个一维的坐标轴，起点处的坐标为0。这条路上有一些限速牌，两个相邻限速牌之间的限速为先出现（坐标较小）的那个限速牌的限速。题中的限速（输入的a）指：走一单位长度所需要的时间。现在可以移走最多k个限速牌，问移走这最多k个限速牌后，走完整条路所需要的最少时间为多少。保证输入的第一个坐标为0，而且0处的限速牌不能移除。
虽然这题数据量很小，一看就知道大概率是DP，但状态及转移比较难想，先想了一下能不能贪心。想了想，错误地认为只要一个前缀的最终速度最快，就能保证全局耗时最少，结果写完马上意识到出错了，因为如果一直把前面慢的删掉，如果中途出现了更慢的就没机会删了。
然后才开始想DP。这时已经稍微有了一点想法：令dp[i][j]为：在第i个路标以前的路段删掉j个路标后，从0走到第j个路标所需最短时间。虽然有想法，但想法不成熟，最开始我还在想这个第i个路标的去留应该怎么处理，还专门将各个dp对应的最终速度村了下来以便状态转移，后面才想到：第i个路标以前的路段，跟第i个路标本身是无关的，在更新dp[i][]的时候压根就用不到路标i的限速，路标i的限速只在更新后面的限速时用到。
各个dp[i][j]所对应的后续速度也都是a[i]，然后就可以写出状态转移方程了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| for (i = 1; i <= n; i++)
{
for (j = 0; j < i; j++)
{
dp[i][j] = 2e9;
for (t = i - (j + 1); t < i; t++)
{
if (j - (i - 1 - t) < t || j - (i - 1 - t) == 0)
dp[i][j] = min(dp[i][j], dp[t][j - (i - 1 - t)] + a[t] * (d[i] - d[t]));
}
}
}
|
完整的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
int dp[505][505], d[505], a[505];
int main()
{
int n, k, l, i, j, t;
scanf("%d%d%d", &n, &l, &k);
for (i = 0; i < n; i++)
scanf("%d", &d[i]);
d[n] = l;
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
for (i = 1; i <= n; i++)
{
for (j = 0; j < i; j++)
{
dp[i][j] = 2e9;
for (t = i - (j + 1); t < i; t++)
{
if (j - (i - 1 - t) < t || j - (i - 1 - t) == 0)
dp[i][j] = min(dp[i][j], dp[t][j - (i - 1 - t)] + a[t] * (d[i] - d[t]));
}
}
}
int res = 2e9;
for (i = 0; i <= k; i++)
res = min(res, dp[n][i]);
printf("%d", res);
return 0;
}
|
需要注意的是：取最终结果时，取的值不一定是拿掉了k个限速牌的值，比如：如果限速牌的限速一直变快，那么一个限速牌都不应该取走。这里取的dp[i][j]表示“在第i个路标以前的路段恰好删掉j个路标后，从0走到第j个路标所需最短时间”，而不是“在第i个路标以前的路段最多删掉j个路标后，从0走到第j个路标所需最短时间”，选这两个状态的代码写法非常相似，但这可以说是截然不同的两种方法，写的时候也千万要注意不能搞混这两个状态，不然很难看出问题。