题解：P14508 猜数游戏 guess

_2eyks · 2025-11-15 16:09:59 · 题解

这个题有点难啊。

考虑分治，如果希望得出 [1,n] 内的答案位置，可以选择一个 t\in[1,n)，将答案区间拆成 [1,t],(t,n] 做。

那么就可以设 f_i 表示 [1,i] 内找出答案，且最后到了 1 或 i+1 位置的最小花费。

转移有 f_i=\min(\max(f_j,f_{i-j})+g_j)，其中 g_j 是向一个方向移动 j 步的最小代价，可以背包求。

假设 a 的值域是 V，注意到移动 >V 步一定需要用 2 个以上的操作，所以转移时 j 的范围上界只要到 V。时间复杂度 \Theta(TnV)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pii pair<int,int>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,r,l) for(int i=r;i>=l;i--)
const int N=2e4+5,V=1e4;
int T,n,m,a[N],b[N],f[N],g[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>T>>T;
    while (T--){
        cin>>n>>m;
        fo(i,1,m)
            cin>>a[i];
        fo(i,0,V*2)
            g[i]=1e18;
        g[V]=0;
        fo(i,1,m){
            cin>>b[i];
            fo(j,a[i],V*2)
                g[j]=min(g[j],g[j-a[i]]+b[i]);
            ro(j,V*2-a[i],0)
                g[j]=min(g[j],g[j+a[i]]+b[i]);
        }
        fo(i,2,n){
            f[i]=1e18;
            fo(j,1,min(i-1,V))
                f[i]=min(f[i],max(f[j],f[i-j])+g[j+V]);
        }
        if (f[n]==1e18)
            cout<<"-1\n";
        else cout<<f[n]<<'\n';
    }
    return 0;
}