题解：P11290 【MX-S6-T2】「KDOI-11」飞船

显然 $x_i=1$ 的加油站不可能使用。因为速度没变，而且还多浪费了 $t_i$ 的时间。

而且注意到同一种 $x$ 的加油站最多只会使用 $\log_x V$ 次。比如已经使用了 $40$ 次 $x_i=2$ 的加油站了，也就是说此时你的速度至少是 $2^{40}$。而此时距离终点最多 $10^9$，也就是不需要 $1$ 秒就能到达。但是再使用一次 $x_i=2$ 的加油站所花的时间 $t_i \ge 1$，一定不优。

所以考虑 DP。设 $f(i, a, b, c)$ 表示到达第 $i$ 个加油站，且已经用了 $a$ 个 $x=2$，$b$ 个 $x=3$，$c$ 个 $x=4$ 的加油站，最小花费时间是多少。这个状态存在的前提是 $2^a \times 3^b \times 4^c \le 10^9$。算一下这样的 $(a, b, c)$ 的数量 $\le 2000$。

转移极易。对于计算答案，找到终点 $y$ 前的最后一个加油站 $x$，枚举此时的 $(a, b, c)$ 即可。

好对啊好对啊。时间复杂度 $\mathcal O(n \log_2 V \log_3 V \log_4V)$。洛谷神机 2s 跑 $2 \times 10^8$ 稳啦。

但注意到 $2 \times 10^8$ 个 `float`/`double` 空间开不下。考虑滚动数组。这样询问就必须离线了。

```cpp
#include "bits/stdc++.h"

using namespace std;

#define int long long

const int N = 1e5 + 10;

int n, q;
double f[2][2000];

struct Node {
  int t, p, x;
}a[N];

int cnt;

double calc(int x, int y, int z) {
  double res = 1;
  while (x -- ) res *= 2;
  while (y -- ) res *= 3;
  while (z -- ) res *= 4;
  return res;
}

void chkmin(double &x, double y) {
  x = x < y ? x : y;
}

vector<int> Q, QQ, id;
double res[N];

struct IJK {
	int j, k, t, val;
};
vector<IJK> S;
int di[100][100][100];

signed main() {
	cnt = 0;
	for (int i = 0; i < 35; ++ i )
		for (int j = 0; j < 25; ++ j )
			for (int t = 0; t < 20; ++ t )
				if (calc(i, j, t) <= 2e9) {
					di[i][j][t] = S.size();
					S.push_back({i, j, t, (int)calc(i, j, t)});
				}
	
  cin >> n >> q;
  for (int i = 1; i <= n; ++ i ) {
    int t, p, x;
    cin >> p >> t >> x;
    if (x != 1) a[ ++ cnt] = {t, p, x};
  }
  n = cnt;
  
  for (int i = 0; i < q; ++ i ) {
  	int y;
  	cin >> y;
  	Q.push_back(y);
  	id.push_back(i);
  	QQ.push_back(y);
  	res[i] = 1e20;
  }
  
  sort(id.begin(), id.end(),
  	[&](int x, int y) {
  		return Q[x] < Q[y];
  	});
  sort(QQ.begin(), QQ.end());
	
  for (int i = 0; i < 2; ++ i )
    for (int j = 0; j < 2000; ++ j )
			f[i][j] = 1e20;

f[0][0] = 0;
  a[n + 1].p = 2e9;
  
  for (int i = 0; i < q; ++ i ) {
  	res[i] = Q[i];
  }
  
  for (int i = 1; i <= n; ++ i ) {
  	int L = lower_bound(QQ.begin(), QQ.end(), a[i].p) - QQ.begin();
  	int R = lower_bound(QQ.begin(), QQ.end(), a[i + 1].p) - QQ.begin() - 1;
  	
  	for (auto e : S) {
  		int j = e.j, k = e.k, t = e.t;
      // 这个是否加速
      f[i & 1][di[j][k][t]] = f[i - 1 & 1][di[j][k][t]] + 1.0 * (a[i].p - a[i - 1].p) / e.val;
      if (j && a[i].x == 2) {
        chkmin(f[i & 1][di[j][k][t]], f[i - 1 & 1][di[j - 1][k][t]] + a[i].t + (a[i].p - a[i - 1].p) * 2.0 / e.val);
      }
      if (k && a[i].x == 3) {
        chkmin(f[i & 1][di[j][k][t]], f[i - 1 & 1][di[j][k - 1][t]] + a[i].t + (a[i].p - a[i - 1].p) * 3.0 / e.val);
      }
      if (t && a[i].x == 4) {
        chkmin(f[i & 1][di[j][k][t]], f[i - 1 & 1][di[j][k][t - 1]] + a[i].t + (a[i].p - a[i - 1].p) * 4.0 / e.val);
      }
    
	    for (int u = L; u <= R; ++ u )
	    	chkmin(res[id[u]], f[i & 1][di[j][k][t]] + 1.0 * (QQ[u] - a[i].p) / e.val);
    }
  }

for (int i = 0; i < q; ++ i ) {
  	cout << fixed << setprecision(7) << res[i] << '\n';
  }

return 0;
}
```

正在渲染内容...