题解：P14508 猜数游戏 guess

Night_sea_64 · 2025-11-15 13:24:41 · 题解

场上来晚了，最后 20min 才胡出来，赶紧开写过了大样例就不管了。但挂成 48pts，原因是极值太小了！谴责大样例没有任何答案爆 int 的数据。

因为 a_i\le 1000，相同的 a_i 显然选择 b_i 更小的，所以本质不同的移动只有 1000 种。

考虑设计一个 dp。容易发现当前的最优步数仅与有可能成为答案的区间的长度有关，不与现在的位置有关，所以 dp 状态只有一维：f_i 表示长度为 i 时的答案。

然后转移的时候可以枚举 1000 种移动方式。复杂度 O(nV)（V 为值域）。

但是这个 dp 不能很好的处理走到区间外面的情况。于是我们干脆更改移动方式，把先走到区间外面再走回来的移动看作一次移动。可以用类似不带堆优化的 Dijkstra 算法求出，复杂度 O(V^2)。

注意 Dijkstra 转移时要开到 2000。

然后再 dp 就是对的了。总复杂度 O(nV+V^2)。

#include<iostream>
#include<cmath>
#define int long long
using namespace std;
int cid,t,n,m;
const int nr=1e4+10,W=2010;
bool fl[nr];
int a[nr],b[nr],minn[W];
int f[nr];
signed main()
{
//  freopen("guess5.in","r",stdin);
//  freopen("guess.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>cid>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=2000;i++)minn[i]=1e18;
        for(int i=1;i<=m;i++)cin>>a[i];
        for(int i=1;i<=m;i++)cin>>b[i];
        for(int i=1;i<=m;i++)minn[a[i]]=min(minn[a[i]],b[i]);
        for(int i=1;i<=2000;i++)fl[i]=0;
        while(1)
        {
            bool flag=0;
            int mn=1e9,minid=0;
            for(int i=1;i<=2000;i++)
                if(!fl[i]&&minn[i]<=mn)mn=minn[i],minid=i;
            if(!minid)break;
            fl[minid]=1;
            for(int i=1;i<=2000;i++)
            {
                if(minid+i<=2000)minn[minid+i]=min(minn[minid+i],minn[minid]+minn[i]);
                int now=abs(minid-i);
                minn[now]=min(minn[now],minn[minid]+minn[i]);
            }
        }
        f[1]=0;
        for(int i=2;i<=n;i++)
        {
            f[i]=1e18;
            for(int j=1;j<=min(i-1,2000ll);j++)
                f[i]=min(f[i],max(f[j],f[i-j])+minn[j]);
        }
        if(f[n]<1e18)cout<<f[n]<<'\n';
        else cout<<-1<<'\n';
    }
    return 0;
}