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

看到题目，不难想到朴素 dp：

令 dp_{i,j} 表示到达第 i 个加油站，最终速度为 j 的最小时间。

转移：

但是可能的速度太多了，所以此 dp 是指数级的。

我们注意到，当速度过大时，时间耗费近似为 0。

而题目中有这么一句话：

• 本题使用自定义校验器检验你的答案是否正确，你只需要保证你的答案与标准答案相对或绝对误差不超过 10^{-6} 即可。即如果对每个询问，假设你的答案为 x，而标准答案为 y，都有 \frac{\lvert x-y\rvert}{\max(1,\lvert y\rvert)}\leq 10^{-6}，则你的答案被认为是正确的。

所以，如果速度为 v，则可能的最大耗时为 \dfrac{10^9}{v}，若 \dfrac{10^9}{v} < 10^{-6} 即 v > 10^{15} 时，我们就不用管它了。

而 10^{15} 内可达的所有速度数量为 824 个，题目开了 3.00s 时限，可以通过。

但我们还要一个状态来表示速度过快，所以一共有 825n 个状态。

具体实现上，如果使用 umap 或 map 来存储状态，会爆空间或时间，所以要对这 824 个数编号。

对于查询，二分出距离最远且在 0\sim y 之间的加油站，枚举每种速度即可。

最后请注意不要用 float，精度不够；也不要用 long double，会快乐的 MLE。

code:

#include<bits/stdc++.h>
using namespace std;
int s[32]={0,50,99,146,192,236,278,319,358,396,432,466,499,530,560,588,615,640,663,685,705,724,741,756,770,782,793,802,810,816,820,823},a[32]={50,49,47,46,44,42,41,39,38,36,34,33,31,30,28,27,25,23,22,20,19,17,15,14,12,11,9,8,6,4,3,1};
long long powb[32]={1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163,387420489,1162261467,3486784401,10460353203,31381059609,94143178827,282429536481,847288609443,2541865828329,7625597484987,22876792454961,68630377364883,205891132094649,617673396283947};
int n,q;
const int N=1e5;
int p[N+5],t[N+5],x[N+5];
double dp[N+5][825];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tmp;
    cin>>tmp>>q;
    for(int i=1;i<=tmp;i++){
        int pi,ti,xi;
        cin>>pi>>ti>>xi;
        if(xi==1) continue;
        p[++n]=pi;
        t[n]=ti;
        x[n]=xi;
    }
    for(int i=1;i<825;i++) dp[0][i]=1e18;
    for(int i=0;i<n;i++){
        dp[i+1][824]=dp[i][824];
        for(int j=31;j>=0;j--){
            for(int k=a[j]-1;k>=0;k--){
                int pos;
                if(x[i+1]==2) pos=(k==a[j]-1?824:s[j]+k+1);
                else if(x[i+1]==3) pos=(j==31?824:s[j+1]+k);
                else pos=(k>=a[j]-2?824:s[j]+k+2);
                dp[i+1][pos]=min(dp[i+1][pos],dp[i][s[j]+k]+(double)(p[i+1]-p[i])/(powb[j]<<k)+t[i+1]);
                dp[i+1][s[j]+k]=dp[i][s[j]+k]+(double)(p[i+1]-p[i])/(powb[j]<<k);
            }
        }
    }
    for(int i=1;i<=q;i++){
        int y;
        cin>>y;
        int pos=upper_bound(p+1,p+n+1,y)-p-1;
        double ans=dp[pos][824];
        for(int j=31;j>=0;j--){
            for(int k=0;k<a[j];k++){
                ans=min(ans,dp[pos][s[j]+k]+(double)(y-p[pos])/(powb[j]<<k));
            }
        }
        cout<<fixed<<setprecision(9)<<ans<<"\n";
    }
    return 0;
}