CF 581E Kojiro and Furrari(JZOJ 4689 新车) 动态规划维护贪心

题目大意

现在有一个长度为 M 的数轴，上面有一个起点和一个终点，起点一定在终点左边。现在你要开车从起点到达终点，但是你的油箱只能走长度为S的路程。途中有 N 个加油站，加油站加的汽油有3种，分别为98，95，92，并且一个加油站只能加一种有油，在每个加油站你可以加任意多的油。一开始你加满了98的汽油，现在给定你每个加油站的位置和可以加的油的种类。问能否到达终点，如果可以最少需要加多少92汽油，当加92汽油一样是最少需要加多少95汽油。

M，N≤200000

解题思路

首先，不难发现我们不可能往右走。然后我们可以考虑贪心。对于当前一个加油站，最优策略一 定是走到一个油的编号大于等于它的加油站，如果没有这样的加油站，我们就尽可能走远一点。这样一来，终点也能看成是一个98加油站，方便我们处理。

设 F[i][0,1,2]表示在第 i 个加油站，按照上述贪心策略走到下一个加油站至少需要多少油（无法到达时为正，否则为 0）。0 表示可用 92，95，98；1 表示可用 95，98；2 表示只用 98。读入的时候用一个 Vector 存一下可到达的加油站，做一次 DP，然后每个询问再用 lower_bound 查询。非常好实现。

程序

//YxuanwKeith #include <cstring> #include <cstdio> #include <algorithm> #include <vector> using namespace std; typedef long long LL; const int MAXN = 2e5 + 5; vector<int> D[3]; int E, S, N, M; LL F[3][MAXN]; int Calc(int Ord, int Side) { int Now = lower_bound(D[Ord].begin(), D[Ord].end(), Side) - D[Ord].begin(); return F[Ord][Now] + max(D[Ord][Now] - Side - S, 0); } int main() { scanf("%d%d%d%d", &E, &S, &N, &M); for (int i = 1; i <= N; i ++) { int t, x; scanf("%d%d", &t, &x); if (x >= E) continue; for (int j = 0; j < t; j ++) D[j].push_back(x); } for (int i = 0; i < 3; i ++) { D[i].push_back(E); sort(D[i].begin(), D[i].end()); int Size = D[i].size() - 1; for (int j = Size - 1; j >= 0; j --) F[i][j] = F[i][j + 1] + max(D[i][j + 1] - D[i][j] - S, 0); } for (int i = 1; i <= M; i ++) { int Side; scanf("%d", &Side); if (Calc(0, Side)) printf("-1 -1\n"); else printf("%d %d\n", Calc(1, Side), Calc(2, Side) - Calc(1, Side)); } }