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

分析

记我们选的加油站的下标序列为 a，其中 a_1=0，那么有代价为：\sum\limits_{i=2}^{|a|} t_{a_i}+\frac{p_{a_i}-p_{a_{i-1}}}{\prod\limits_{j=1}^{i-1}x_{a_j}}+\frac{y-p_{a_{|a|}}}{\prod\limits_{j=1}^{|a|}x_{a_j}}。我们把式子化简一下，会发现是：(\sum\limits_{i-1}^{|a|}t_{a_i}+\frac{(x_{a_i}-1)p_{a_i}}{\prod\limits_{j=1}^{i}x_{a_j}})+\frac{y}{\prod\limits_{j=1}^{|a|}x_{a_j}}。不难发现，当 \prod\limits_{j=1}^{|a|}x_{a_j} 一定时，只需要满足前面的式子的值最小就行了。

注意到精度只有 10^{-6}，也就是说，当 \prod\limits_{j=1}^{|a|}x_{a_j} 大到某个值时，再大是对答案没有贡献的。粗略算一下大概为 10^{15}。因为 x_i=1 的加油站没用，所以最终可能的值的数量等于用 2,3,4 乘起来得到的值 \le 10^{15} 的数量。暴力搜索可以得到是 824 个（算了 1 这个值）。所以就可以直接跑背包解决了。时间复杂度 O(na)，a=824。

代码

il void solve(){
    dfs(1),sort(v.begin(),v.end()),vis.clear();
    int len=(int)(v.size());
    for(re int i=0;i<len;++i) f[i]=1000000000000000.0,vis[v[i]]=i;
    f[0]=0.0;
    n=rd,q=rd;
    for(re int i=1;i<=n;++i) cin>>p[i]>>t[i]>>x[i];
    for(re int i=1;i<=q;++i) cin>>Q[i].y,Q[i].id=i;
    sort(Q+1,Q+q+1),p[n+1]=1e18;
    for(re int i=1,j=1;i<=n+1;++i){
        while(j<=q&&Q[j].y<p[i]){
            double Min=1000000000000000.0;
            for(re int k=0;k<len;++k){
                Min=min(Min,f[k]+(double)(Q[j].y*1.0/v[k]));    
            }
            ans[Q[j].id]=Min;
            ++j;
        }
        if(i<=n&&x[i]>1){
            for(re int k=len-1;k>=1;--k){
                if((int)v[k]%(int)x[i]==0) f[k]=min(f[k],f[vis[v[k]/x[i]]]+(double)((x[i]-1)*p[i]*1.0/v[k])+t[i]);
            }
        }
    }
    for(re int i=1;i<=q;++i) printf("%.10lf\n",ans[i]);
    return ;
}