题解：P14508 猜数游戏 guess

hepp · 2025-11-15 14:45:20 · 题解

出题人题解。

设 d_i 为跳的长度为 i 的花费，注意到跳 x 步等同于跳过去 y 步再跳回来 y-x 步。注意到很像最短路的形式，可以用最短路跑出所有的 d_i，然后有转移式 f_i=\min_{j=1}^{i-1}(d_j+\max(f_{i-j},f_j))。答案即为 f_n。时间复杂度 O(n\times(n+m))，实现的好可以通过。

考虑优化，注意到 i>\max a_i 时一定是由两步以上跳过来的，所以我们只需要记录 i 小于等于 \max a_i 的 d_i，转移和上面一样，是简单的。时间复杂度 O(m\times(n+m))。

代码比较劣，主要是堆劣化迪杰，以及考虑了棋子在左边还是右边的情况——事实证明不需要。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+10,M=1010,inf=1e18;
int n,m,c,T,a[M],b[M];
int d[M<<1],vis[M<<1],f[N][2];
struct node{
    int id,dis;
    bool operator<(const node &y)const
        {return dis>y.dis;}
};priority_queue<node>q;
bool check(int x,int y){
    if(x==0&&y==0) return 0;
    return y<=2000&&y>=0&&vis[y]==0;
}
signed main(){
    cin>>c>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=m;i++) cin>>a[i];
        for(int i=1;i<=m;i++) cin>>b[i],q.push({a[i],b[i]});
        for(int i=1;i<=2000;i++) d[i]=inf,vis[i]=0;
        while(q.size()){
            node u=q.top(); q.pop();
            if(vis[u.id]) continue;
            d[u.id]=u.dis,vis[u.id]=1;
            for(int i=1;i<=m;i++){
                int x=u.id+a[i],y=u.id-a[i];
                if(check(u.id,x)&&d[x]>d[u.id]+b[i])
                    d[x]=d[u.id]+b[i],q.push({x,d[x]});
                if(check(u.id,y)&&d[y]>d[u.id]+b[i])
                    d[y]=d[u.id]+b[i],q.push({y,d[y]});
            }
        }
        f[0][0]=f[0][1]=f[1][0]=f[1][1]=0;
        for(int i=2;i<=n;i++){
            f[i][1]=f[i][0]=inf;
            for(int j=1;j<=min(i-1,1000ll);j++){
                f[i][1]=min(f[i][1],max(f[j][0],f[i-j][1])+d[j]);
                f[i][0]=min(f[i][0],max(f[j][1],f[i-j][0])+d[j]);
            }
        }
        cout<<(f[n][1]==inf?-1:f[n][1])<<'\n';
    }
    return 0;
}