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

刚开始看出来应该可以用 dp 了，但是因为某些原因没想到速度是可以放到状态里面的。

首先考虑 x\in\{1,2\} 的情况，容易发现在每一个时刻飞船的速度都是 2 的整数次幂。因此，在 10^9 范围内的可能的速度实际上很少。既然这样，就可以把速度的幂次放到 dp 的状态里。设 dp_{i,j} 表示到达第 i 个加油站且速度为 2^j 时最少需要的时间。对于每个加油站，可以选择加或者不加，计算出对应时间再取最小值即可。

注意到全部数据范围的 x\in\{1,2,3,4\}，所以只需要增加一维表示速度中有 3 的几次幂即可。用同样的方式转移，注意不要数组越界就行了。

但是这题空间卡的比较紧，即使用 double 也有 MLE 的可能，最好是把询问离线下来，再用滚动数组优化一下 dp，在 dp 过程中直接计算出所有询问的答案，就不需要把所有 dp 值存下来了。

既然都用滚动数组优化了，也不用担心空间的问题了，不如用精度更高的 long double。

具体可以见代码注释。

#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N=1e5+5;
int pp[N],tt[N],xx[N];
double dp[2][32][21];
double p2[35],p3[25];
double ans[N];
pair<int,int>qu[N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    p2[0]=p3[0]=1;//预处理出 2 和 3 的幂次
    for(int i=1;i<=32;i++)p2[i]=p2[i-1]*2;
    for(int i=1;i<=23;i++)p3[i]=p3[i-1]*3;
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>pp[i]>>tt[i]>>xx[i];
    }
    for(int i=0;i<=1;i++)for(int j=0;j<=31;j++)for(int k=0;k<=20;k++)dp[i][j][k]=1e18;
    dp[0][0][0]=0;//注意初始化
    for(int i=1;i<=q;i++){
        cin>>qu[i].first;qu[i].second=i;
    }
    sort(qu+1,qu+1+q);
    int ppp=1;
    for(int i=1;i<=n;i++){
        double p=pp[i],t=tt[i],lp=pp[i-1];
        int x=xx[i];
        while(ppp<=q&&qu[ppp].first<p){//处理现在需要解决的所有询问（等一下这些要用到的 dp 值就滚走了）
            double an=1e18;
            for(int j=0;j<=31;j++){
                for(int k=0;k<=20;k++){
                    an=min(an,dp[0][j][k]+(qu[ppp].first-lp)/p2[j]/p3[k]);//路程 / 速度 = 时间
                }
            }
            ans[qu[ppp].second]=an;
            ppp++;
        }
        for(int j=31;j>=0;j--){
            for(int k=20;k>=0;k--){
                dp[1][j][k]=dp[0][j][k]+(p-lp)/p2[j]/p3[k];//路程 / 速度 = 时间
            }
        }
        for(int j=31;j>=0;j--){
            for(int k=20;k>=0;k--){//注意这里的转移顺序
                switch(x){
                    case 1:
                        break;//x=1，不用管
                    case 2:
                        if(j>0)dp[1][j][k]=min(dp[1][j][k],dp[1][j-1][k]+t);
                        break;//x=2，如果在这里加了油，那么原来的速度应该是 2^(j-1)*3^k
                    case 3:
                        if(k>0)dp[1][j][k]=min(dp[1][j][k],dp[1][j][k-1]+t);
                        break;//x=3，如果在这里加了油，那么原来的速度应该是 2^j*3^(k-1)
                    case 4:
                        if(j>1)dp[1][j][k]=min(dp[1][j][k],dp[1][j-2][k]+t);
                        break;//x=4，如果在这里加了油，那么原来的速度应该是 2^(j-2)*3^k
                } 
            }
        }
        for(int j=31;j>=0;j--){
            for(int k=20;k>=0;k--){
                dp[0][j][k]=dp[1][j][k];
            }
        }
    }
    while(ppp<=q){//最后一个加油站右边的询问别忘了处理
        double an=1e18;
        for(int j=0;j<=31;j++){
            for(int k=0;k<=20;k++){
                an=min(an,dp[0][j][k]+(qu[ppp].first-pp[n])/p2[j]/p3[k]);
            }
        }
        ans[qu[ppp].second]=an;
        ppp++;
    }
    cout<<fixed<<setprecision(10);
    for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
    return 0;
}

要注意询问总数是 q 不是 n，排序的时候别用成 sort(qu+1,qu+1+n) 了，这样会挂成 45 分，别问我怎么知道的。