P11290Solution

· · 题解

写的时候看成起点也是给定的还有救吗 QAQ

注意到 x 仅有 4 种情况，并且质数仅为 2 和 3，那么最后的速度一定是形如 2^p3^q 这样的速度。若想到 DP 的话，那么启发我们可以设两维 i,j 分别表示因数为 2 的有 j 个，因数为 3 的有 k 个这个速度所需时间最小的值。于是，第一维理所应当的设为考虑到第 i 个加油站时的最小值。于是有 DP 数组形式 f[i][j][k]。

那么接下来考虑怎么转移。

分情况将几种类型递推 比如 2 可以有取和不取两种情况，对应到从 f[i-1][j-1][k] 转移和从 f[i-1][j][k] 转移两种情况。其它类型的 x 值类似，这里就讨论一种，其它情况相同方法推广即可。问题在于从上一个位置转移的贡献，容易想到经过路程一定要加上为 \frac{\text{从上一个状态转移的路程}}{\text{上一个转移状态的速度}}，最后如果要加油还要加上加油的时间 t，最后取最小值。

初始化 f[0][0][0] 为 0，其余赋值为最大值进行转移。

然后预处理完找与终点最近的一个加油站枚举因数求最小值即可。

然后愉快的发现 MLE 了。

本题卡了空间所以要滚动数组滚掉第一维，把询问离线下来再转移即可。

时间复杂度是 O(n\log^2{V} + q\log^2{V}) 其中 V 为值域大小。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+10;
double f[MAXN][50][41];
double p[MAXN],t[MAXN],x[MAXN];
int n,q;
double ms[50][41];
double ans[MAXN];
struct ask{
    double y;int id;
};
vector<ask>Q;
int main(){
    scanf("%d%d",&n,&q);
    for(int i=0;i<=49;++i)for(int j=0;j<=40;++j)f[0][i][j]=1e18;
    f[0][0][0]=0;
    for(int i=1;i<=n;++i)scanf("%lf%lf%lf",&p[i],&t[i],&x[i]);
    ms[0][0]=1;
    for(int i=1;i<=49;++i)ms[i][0]=ms[i-1][0]*2.0;
    for(int i=0;i<=49;++i)
        for(int j=1;j<=40;++j)
            ms[i][j]=ms[i][j-1]*3.0;
    for(int i=1;i<=q;++i){
        double y;scanf("%lf",&y);Q.push_back(ask{y,i});
    }
    sort(Q.begin(),Q.end(),[](ask a,ask b){return a.y<b.y;});
    int i=0;
    p[n+1]=1e18;
    for(ask a:Q){
        while(p[i+1]<a.y){++i;
        for(int j=0;j<=49;++j)
            for(int k=0;k<=40;++k){
                f[i&1][j][k]=f[(i&1)^1][j][k]+((p[i]-p[i-1])/ms[j][k]);
                if(x[i]==1)continue;
                if(x[i]==2&&j>0)f[i&1][j][k]=min(f[i&1][j][k],f[(i&1)^1][j-1][k]+t[i]+((p[i]-p[i-1])/ms[j-1][k]));
                if(x[i]==3&&k>0)f[i&1][j][k]=min(f[i&1][j][k],f[(i&1)^1][j][k-1]+t[i]+((p[i]-p[i-1])/ms[j][k-1]));
                if(x[i]==4&&j>1)f[i&1][j][k]=min(f[i&1][j][k],f[(i&1)^1][j-2][k]+t[i]+((p[i]-p[i-1])/ms[j-2][k]));
            }
        }ans[a.id]=1e18;
        for(int j=0;j<=49;++j)
            for(int k=0;k<=40;++k)
                ans[a.id]=min(ans[a.id],(a.y-p[i])/ms[j][k]+f[i&1][j][k]);
    }
    for(int i=1;i<=q;++i)printf("%.9lf\n",ans[i]);
    return 0;
}