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

· · 题解

前言

典中典。

Solution

显然速度达到一定大小的时候再往上加一定不优，由 t=\frac{x}{v} 即可得出。

我们可以设个上限值，然后在上限值范围内进行 dp。

但是我们发现 v 的取值还是有点大，注意到题目中的加粗字 1\le x\le 4，这说明组成 v 的质因数只有 2 和 3。

于是我们可以设 f_{i,j,k} 为经过前 i 个加油站，当前 v=2^j\times 3^k 时的最小时间，转移方程比较显然就不写了。

然后就做完了，时间复杂度为 O(n \log^2 V)，如果害怕空间爆掉可以写个滚动数组。

Code

#include<bits/stdc++.h>
#include<cmath>
#define ll long long
#define lll __int128
#define ull unsigned long long
#define N 100010
#define For(i,a,b) for(int i=a;i<=b;++i)
#define Rof(i,a,b) for(int i=a;i>=b;--i)
#define ls x<<1
#define rs x<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r 
#define pb push_back
#define mk make_pair
#define pque priority_queue
#define pii pair<int,int>

using namespace std;
bool st;
const double inf=1e12;
double f[2][35][35];
struct node{
    int x,t,num;
}a[N];
struct ask{
    int t,bh;
}b[N];
double ans[N];
int n,q;
bool ed;

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main()
{
    //fprintf(stderr,"%.2lf",(double)(&ed-&st)/1024/1024);
    //freopen("ship.in","r",stdin);
    //freopen("ship.out","w",stdout);
    n=read(),q=read();
    For(i,1,n) a[i].x=read(),a[i].t=read(),a[i].num=read();
    For(i,1,q) b[i].t=read(),b[i].bh=i;
    sort(b+1,b+q+1,[&](ask x,ask y){return x.t<y.t;});
    For(i,0,1){
        For(j,0,34){
            For(k,0,34){
                f[i][j][k]=inf;
            }
        }
    }
    f[0][0][0]=0;
    int now=0;
    For(i,1,q){
        while(now<n && a[now+1].x<=b[i].t){
            int op=now&1;
            double now1=1;
            For(j,0,34){
                double now2=now1;
                For(k,0,34){
                    if(now2>inf) break;
                    f[op^1][j][k]=f[op][j][k]+(double)(a[now+1].x-a[now].x)*1.0/now2;
                    now2*=3;
                }
                now1*=2;
            }
            int p1=0,p2=0;
            if(a[now+1].num==2) p1=1;
            else if(a[now+1].num==3) p2=1;
            else if(a[now+1].num==4) p1=2;    
            now1=1;
            For(j,0,34-p1){
                double now2=now1;
                For(k,0,34-p2){
                    if(now2>inf) break;
                    f[op^1][j+p1][k+p2]=min(f[op^1][j+p1][k+p2],f[op][j][k]+(double)(a[now+1].x-a[now].x)*1.0/now2+(double)a[now+1].t);
                    now2*=3;
                }
                now1*=2;
            }
            now++;
        }
        double now1=1,nowans=inf;
        For(j,0,34){
            double now2=now1;
            For(k,0,34){
                if(now2>inf) break;
                nowans=min(nowans,f[now&1][j][k]+(double)(b[i].t-a[now].x)*1.0/now2);
                now2*=3;
            }
            now1*=2;
        }
        ans[b[i].bh]=nowans;
    }
    For(i,1,q) printf("%.10lf\n",ans[i]);
    return 0;
}
/*

*/