猜数游戏 guess

· · 题解

前言

:::error[致歉] 之前写的完全背包做法，是错误的，已经改为最短路做法。有错误欢迎指出。 :::

题目分析

首先我们发现我们可以移动一段距离，获得这一段有没有。同时继续处理子问题。于是我们可以考虑 DP。

设 f_i 表示长度为 i 的区间（假设是 [1,i]）当前在 1 或者 i+1 时最少步数。

我们考虑转移，假设跳了长为 j 的区间，可以从 f_j,f_{i-j} 转移。

我们现在需要处理的就是考虑移动长度为 x 需要的代价。这个不可以完全背包。

这个可以按照要求直接跑最短路，完全背包时错的因为完全背包的决策时一个物品走到底，这不能利用一定有一个选的方案在范围内。

时间复杂度 O(T(n^2+nm\log nm))。

代码

#include<bits/stdc++.h>
#define int long long
#define ALL(x) x.begin(),x.end()
#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
using namespace std;
__inline void read(int&x){
    x=0;
    char ch=getchar();
    while(!isdigit(ch))
        ch=getchar();
    while(isdigit(ch))
        x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return;
}
__inline void write(int val){
    if(val<0){
        putchar('-');
        return write(-val);
    }
    if(val>=10)
        write(val/10);
    putchar((val%10)^48);
    return;
}
__inline void writeln(int x){
    write(x);
    putchar('\n');
    return;
}
constexpr int N=1e4+2,Inf=0x3f3f3f3f3f3f3f3fll;
int C,T,n,m,a[N],b[N],dis[N<<1],cost[N],f[N];
void dijkstra(){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
    memset(dis,0x3f,sizeof(dis));
    q.push({dis[N]=0,N});
    while(!q.empty()){
        auto[d,u]=q.top();
        q.pop();
        if(dis[u]!=d)
            continue;
        for(int i=1;i<=m;i++){
            if(0<=u-a[i]&&d+b[i]<dis[u-a[i]])
                q.push({dis[u-a[i]]=d+b[i],u-a[i]});
            if(u+a[i]<(N<<1)&&d+b[i]<dis[u+a[i]])
                q.push({dis[u+a[i]]=d+b[i],u+a[i]});
        }
    }
    return;
}
void Main(){
    memset(f,0x3f,sizeof(f));
    read(n),read(m);
    for(int i=1;i<=m;i++)
        read(a[i]);
    for(int i=1;i<=m;i++)
        read(b[i]);
    dijkstra();
    for(int i=0;i<N;i++)
        cost[i]=dis[N+i];
    f[0]=f[1]=0;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++)
            f[i]=min(f[i],max(f[j],f[i-j])+cost[j]);
    }
    writeln(f[n]==Inf?-1:f[n]);
    return;
}
signed main(){
    for(read(C),read(T);T;--T)
        Main();
    return 0;
}