题解：P14508 猜数游戏 guess

· · 题解

看到题，第一反应是建模图论。记 A=\max_{i=1}^ma_i，显然有效的移动只会在[-A,n+A] 内进行，于是考虑把区间内部的每个位置等效到一个点，对于每个点连 2m 条边对应走法，求走遍 1\sim n 每个点的最短距离，即能够保证对于每个点而言都存在某次移动的询问边界取到它本身，即每个点存在一个不同于其他点的询问返回值。

但是这个东西看起来是非常不可做的，于是我们需要另辟蹊径。

考虑到这个棋盘是无穷大且重复的，我们要求 [i,j] 下的答案，它与平移到第一位求 [1,j-i+1] 没有本质不同，注意到这是一个非常完美的最优子结构性质，于是考虑进行动态规划。

我们定义 dp_i 表示解决 [1,i] 区间内的问题需要的最小代价。[1,i] 根据第一次移动可以被划分为 [1,j]，[j+1,i] 进行求解。

我们先从 1 移动到 j，最少花费 dis_j 的代价。这个时候进行分类讨论，如果答案不在 [1,j]，我们就在 [j+1,i] 中寻找答案，这部分可以通过平移化为 [1,i-j]。如果答案在 [1,j] 中，那么我们就再在 [1,j] 中求解。因此要取 dp_j 与 dp_{i-j} 中较大的一个。

于是得到转移方程：

dp_i=\mathop{\text{min}}\limits_{j=1}^{i-1}\{\text{max}\{dp_i,dp_{i-j}\}+dis_{j}\}

计算 dis_j 的过程可以使用堆优化的最短路进行求解（注意不能使用先加后减的多重背包），时间复杂度 \Theta(mA\log mA)，动态规划的时间复杂度 \Theta(n^2)，会超时，考虑优化。

发现其实转移时，如果 j 超过了 A，本质上是从 dp_j 跳了好几步走到 dp_i，这部分直接舍去即可。于是动态规划时间复杂度优化到了 \Theta(nA)，多测情况下可以通过该题。

注意几个实现时的细节：

  1. 代价极限数据下会超过 int 的数据范围，需要开 ll。

  2. 最短路由于在进行松弛操作时可能会出现下标为负的点，因此考虑将所有点右移 A 位后再进行求解，动态规划时候还原。

  3. 如果暴力建图再进行最短路会导致总边数上界达到 6nmT 导致 \text{MLE}，因此需要在最短路松弛操作内部直接根据 m 进行遍历。

AC Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e4+10;
const int maxm=5e3+10;
typedef long long ll;
const ll INF=1e18;
int n,m,mxk,mnk;
ll dp[maxn],dis[maxm<<2];
struct move
{
    int k;
    ll v;
}mov[maxm];
struct edge
{
    int v;
    ll w;   
};
struct node
{
    int k;
    ll dis;
    bool operator <(const node &uu)const
    {
        return dis>uu.dis;
    }   
};
priority_queue<node>q;
int vis[maxm<<2];
void dijkstra()
{
    for(int i=0;i<=2*n+1;i++)
        dis[i]=INF,vis[i]=0;
    dis[mxk]=0;
    q.push({mxk,0}); 
    while(!q.empty())
    {
        int k=q.top().k;
        q.pop();
        if(vis[k])
            continue;
        vis[k]=1;
        for(int i=1;i<=m;i++)
        {
            if(k-mov[i].k<0)
                continue;
            int to=k-mov[i].k;
            ll w=mov[i].v;
            if(dis[k]+w<dis[to])
            {
                dis[to]=dis[k]+w;
                q.push({to,dis[to]});
            }
        }
        for(int i=1;i<=m;i++)
        {
            if(k+mov[i].k>2*n+1)
                continue;
            int to=k+mov[i].k;
            ll w=mov[i].v;
            if(dis[k]+w<dis[to])
            {
                dis[to]=dis[k]+w;
                q.push({to,dis[to]});
            }
        }
    }
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    int c,t;
    cin>>c>>t;
    while(t--)
    {
        mxk=0,mnk=INF;
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>mov[i].k;
            mxk=max(mxk,mov[i].k);
            mnk=min(mnk,mov[i].k);
        }
        for(int i=1;i<=m;i++)
            cin>>mov[i].v;
        dijkstra();
        fill(dp,dp+1+n,INF);
        dp[1]=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=min(i-1,mxk);j++)
                dp[i]=min(dp[i],max(dp[j],dp[i-j])+dis[j+mxk]);
//      for(int j=0;j<=min(n,mxk);j++)
//          cout<<j<<"v "<<dis[j+mxk]<<endl;
        if(dp[n]==INF)
            cout<<-1<<endl;
        else
            cout<<dp[n]<<endl;
    }
    return 0;
}