专栏文章

题解：P14508 猜数游戏 guess

__2eyks
P14508题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min7ou8g
此快照首次捕获于
2025/12/01 21:55
3 个月前
此快照最后确认于
2025/12/01 21:55
3 个月前
查看原文
这个题有点难啊。
考虑分治，如果希望得出 [1,n][1,n] 内的答案位置，可以选择一个 t∈[1,n)t\in[1,n)，将答案区间拆成 [1,t],(t,n][1,t],(t,n] 做。
那么就可以设 fif_i 表示 [1,i][1,i] 内找出答案，且最后到了 11 或 i+1i+1 位置的最小花费。
转移有 fi=min⁡(max⁡(fj,fi−j)+gj)f_i=\min(\max(f_j,f_{i-j})+g_j)，其中 gjg_j 是向一个方向移动 jj 步的最小代价，可以背包求。
假设 aa 的值域是 VV，注意到移动 >V>V 步一定需要用 22 个以上的操作，所以转移时 jj 的范围上界只要到 VV。时间复杂度 Θ(TnV)\Theta(TnV)。
CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...