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

· · 题解

这题我赛时没想出正解，在赛后才明白怎么做。

首先通过推导公式，发现该题无法贪心。

然后我想到一个 dp，以第几个加油站为第一维，以速度为第二维，可以轻松通过速度转移状态。但是这样 dp 会使速度达到指数级别，简直爆炸。

赛后我反应过来，虽然速度的值域看似达到指数级，但速度的个数远远没有达到这种数量。为什么呢？

首先我们发现速度值域根本没有这么大，因为如果速度过大，会导致加速减少的时间很少，而在加油上浪费了更多的时间，不是最优解。而加速减少的时间至少为 1，即速度值域上界则为 p 的值域上界。

但这样也 AC 不了。我们继续推导发现燃油编号为 1 可以忽略不计，为 4 可以拆成两个 2，所以速度一定是 2 的非负整数次方乘上 3 的非负整数次方。

这样 dp 就很好转移了。第一维表示第几个加油站，第二维表示 2 的指数，第三维则表示 3 的指数，然后通过加油站转移状态即可。查询时，首先找到最后一个小于等于目标节点的加油站（可以使用二分），然后从这个加油站的每个状态转移出答案，并取最小值即可。

这样我们就得到了一个 O(n\log^2 n) 的算法。由于空间耗用较大，考虑使用滚动数组优化 dp，且把询问离线下来升序排序，边转移边处理询问，这会把空间优化至线性，还会意外地使时间得到优化。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005][3],x,y,z,num=1,g2[5]={0,0,1,0,2},g3[5]={0,0,0,1,0};
long long p2[30],p3[19];
double c[30][19],d[30][19],aans,ans[100005];
struct node
{
    int id,x;
} b[100005];
bool operator<(node x,node y)
{
    return x.x<y.x;
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;++i)
    scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
    a[n+1][0]=0x7fffffff;
    for (int i=1;i<=m;++i)
    {
        b[i].id=i;
        scanf("%d",&b[i].x);
    }
    sort(b+1,b+m+1);//离线处理
    p2[0]=1;
    p3[0]=1;
    for (int i=1;i<=29;++i)
    p2[i]=p2[i-1]<<1;
    for (int i=1;i<=18;++i)
    p3[i]=3*p3[i-1];//预处理2、3的幂次方
    for (int i=0;i<=29;++i)
    for (int j=0;j<=18 && p2[i]*p3[j]<=1000000000;++j)
    c[i][j]=1e18;
    c[0][0]=0;//预处理
    for (int i=1;i<=n;++i)
    {
        x=a[i][0];
        y=a[i][1];
        z=a[i][2];
        memcpy(d,c,sizeof(c));//滚动数组
        for (int j=0;j<=29;++j)
        for (int k=0;k<=18 && p2[j]*p3[k]<=1000000000;++k)
        {
            c[j][k]=d[j][k]+(double)(x-a[i-1][0])/(p2[j]*p3[k]);
            if (j>=g2[z] && k>=g3[z])
            c[j][k]=min(c[j][k],d[j-g2[z]][k-g3[z]]+(double)(x-a[i-1][0])/(p2[j-g2[z]]*p3[k-g3[z]])+y);
        }//转移速度
        for (num;num<=m && b[num].x<=a[i+1][0];++num)
        {
            aans=1e18;
            for (int j=0;j<=29;++j)
            for (int k=0;k<=18 && p2[j]*p3[k]<=1000000000;++k)
            aans=min(aans,c[j][k]+(double)(b[num].x-x)/(p2[j]*p3[k]));
            ans[b[num].id]=aans;
        }//处理询问
    }
    for (int i=1;i<=m;++i)
    printf("%.9lf\n",ans[i]);//使用printf以减小误差
}