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

这是一个简单的 dp 题。

注意到 1 \le x_i \le 4，所以可以设 f_{i,j,k} 表示到第 i 个加油站，当前速度为 2^j \times 3^k 时至少要花多少时间，加了油转移方程为 f_{i,j,k}=\min(f_{i,j,k},f_{i-1,j-u,k-v}+(p_i-p_j)\div(2^j \times 3^k)+t_i)，其中

• 当 x_i=2 时 u=1,v=0。
• 当 x_i=3 时 u=0,v=1。
• 当 x_i=4 时 u=2,v=0。

没有加油的转移方程是 f_{i,j,k}=\min(f_{i,j,k},f_{i-1,j,k}+(p_i-p_j)\div(2^j \times 3^k)+t_i)

但是每一个加油站只能加一次油，所以我们还需要设 g_{i,j,k} 表示到第 i 个加油站，当前速度为 2^j \times 3^k 的状态是否存在。

回答问题可以二分这个位置左边的加油站，然后再加上剩余的路程除以速度，取最小值。

设 V 为 p_i 的值域，时间复杂度 \mathcal{O}((n+q) \log V^2+q\log n)，可以通过。

注意不要开 long double，会爆内存。

代码：

#include<iostream>
#include<algorithm>
#include<iomanip>

using namespace std;
typedef long long ll;

const int N = 1e5 + 1; const ll mx = 6e9;
int n, q, p[N], t[N], x[N], y, m2[31], m3[19];
bool g[N][31][19];
double f[N][31][19], ans;

int main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> p[i] >> t[i] >> x[i];
    }
    m2[0] = m3[0] = 1;
    for(int i = 1; i < 19; i++) m2[i] = m2[i-1] * 2, m3[i] = m3[i-1] * 3;
    for(int i = 19; i < 31; i++) m2[i] = m2[i-1] * 2;
    g[0][0][0] = 1;
    for(int i = 1; i < N; i++){
        for(int j = 0; j < 31; j++){
            for(int k = 0; k < 19; k++){
                f[i][j][k] = 1e9;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        int n1, n2;
        if(x[i] == 1) n1 = n2 = 0;
        else if(x[i] == 2) n1 = 1, n2 = 0;
        else if(x[i] == 3) n1 = 0, n2 = 1;
        else n1 = 2, n2 = 0;
        for(int w1 = 0; w1 < 31; w1++){
            for(int w2 = 0; w2 < 19; w2++){
                if((ll)m2[w1] * m3[w2] > mx) continue;
                if(n1 <= w1 && n2 <= w2 && g[i-1][w1-n1][w2-n2]){
                    f[i][w1][w2] = min(f[i-1][w1-n1][w2-n2] + (p[i] - p[i-1]) * 1.0 / ((ll)m2[w1-n1] * m3[w2-n2]) + t[i], f[i][w1][w2]);
                    g[i][w1][w2] = 1;
                }
                if(g[i-1][w1][w2]){
                    f[i][w1][w2] = min(f[i-1][w1][w2] + (p[i] - p[i-1]) * 1.0 / ((ll)m2[w1] * m3[w2]), f[i][w1][w2]);
                    g[i][w1][w2] = 1;
                }
            }
        }
    }
    while(q--){
        cin >> y;
        int fd = upper_bound(p, p + n + 1, y) - p - 1;
        ans = 1e9;
        for(int w1 = 0; w1 < 31; w1++){
            for(int w2 = 0; w2 < 19; w2++){
                if((ll)m2[w1] * m3[w2] > mx) continue;
                if(g[fd][w1][w2]){
                    ans = min(ans, f[fd][w1][w2] + (y - p[fd]) * 1.0 / ((ll)m2[w1] * m3[w2]));
                }
            }
        }
        cout << fixed << setprecision(8) << ans << '\n'; //避免用科学计数法输出。 
    }
    return 0;
}

然后你就会发现：

这是因为数组开得太大了，观察到转移方程只跟 i 和 i-1 有关，所以我们可以用滚动数组的方法，先把问题离线并排序，记录它原来的地方，然后在 dp 的过程中记录这些问题的答案，最后按照它原来的地方排序输出，注意 dp 前要清空。

AC 代码：

#include<iostream>
#include<algorithm>
#include<iomanip>

using namespace std;
typedef long long ll;

const int N = 1e5 + 1; const ll mx = 6e9;
int n, q, p[N], t[N], x[N], m2[31], m3[19];
bool g[2][31][19];
double f[2][31][19], ans;

struct Y{
    int y, id; double ans;

    bool operator < (const Y & o) const{
        return y < o.y;
    }
} y[N];

bool cmp(Y xx, Y yy){
    return xx.id < yy.id;
}

void clearfg(int x){
    for(int j = 0; j < 31; j++){
        for(int k = 0; k < 19; k++){
            f[x][j][k] = 1e9; g[x][j][k] = 0;
        }
    }
}

int main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> p[i] >> t[i] >> x[i];
    }
    m2[0] = m3[0] = 1;
    for(int i = 1; i < 19; i++) m2[i] = m2[i-1] * 2, m3[i] = m3[i-1] * 3;
    for(int i = 19; i < 31; i++) m2[i] = m2[i-1] * 2;
    g[0][0][0] = 1;
    for(int i = 0; i < q; i++){
        cin >> y[i].y;
        y[i].id = i;
    }
    sort(y, y + q);
    int idx = 0;
    for(int i = 1; i <= n; i++){
        int n1, n2;
        if(x[i] == 1) n1 = n2 = 0;
        else if(x[i] == 2) n1 = 1, n2 = 0;
        else if(x[i] == 3) n1 = 0, n2 = 1;
        else n1 = 2, n2 = 0;
        clearfg(i&1);
        for(int w1 = 0; w1 < 31; w1++){
            for(int w2 = 0; w2 < 19; w2++){
                if((ll)m2[w1] * m3[w2] > mx) continue;
                if(n1 <= w1 && n2 <= w2 && g[i&1^1][w1-n1][w2-n2]){
                    f[i&1][w1][w2] = min(f[i&1^1][w1-n1][w2-n2] + (p[i] - p[i-1]) * 1.0 / ((ll)m2[w1-n1] * m3[w2-n2]) + t[i], f[i&1][w1][w2]);
                    g[i&1][w1][w2] = 1;
                }
                if(g[i&1^1][w1][w2]){
                    f[i&1][w1][w2] = min(f[i&1^1][w1][w2] + (p[i] - p[i-1]) * 1.0 / ((ll)m2[w1] * m3[w2]), f[i&1][w1][w2]);
                    g[i&1][w1][w2] = 1;
                }
            }
        }
        while(((y[idx].y >= p[i] && y[idx].y < p[i+1]) || i == n) && idx < q){
            ans = 1e9;
            for(int w1 = 0; w1 < 31; w1++){
                for(int w2 = 0; w2 < 19; w2++){
                    if((ll)m2[w1] * m3[w2] > mx) continue;
                    if(g[i&1][w1][w2]){
                        ans = min(ans, f[i&1][w1][w2] + (y[idx].y - p[i]) * 1.0 / ((ll)m2[w1] * m3[w2]));
                    }
                }
            }
            y[idx++].ans = ans;
        }
    }
    sort(y, y + q, cmp);
    for(int i = 0; i < q; i++){
        cout << fixed << setprecision(8) << y[i].ans << '\n';
    }
    return 0;
}