Vanya and Treasure

首先，这个题 O(nm\sqrt{nm}) 太屈才了。

所以，介绍一个 O(nm\log^2(nm)) 的做法。

首先，你可以枚举 i\in[1,p] 转移答案。

转移式子如下：

dp_{x,y}=\min_{p,q}dp_{p,q}+\operatorname{dis}((p,q),(x,y))

其中 a_{x,y}=i,a_{p,q}=i-1。

可以开 p 个 vector，每一次把 (i,j) 放进 a_{i,j} 对应的 vector 中。

这样就是 O(n^2m^2) 的。

然后，你觉得这有点浪费。

因为每一个位置的转移都差不多，考虑全部拼起来。

• 对于第一区域的 (p,q)

  dp_{i,j}=(\min_{p,q} dp_{p,q}-p-q)+i+j

• 对于第二区域的 (p,q)

  dp_{i,j}=(\min_{p,q}dp_{p,q}-p+q)+i-j

• 对于第三区域的 (p,q)

  dp_{i,j}=(\min_{p,q}dp_{p,q}+p+q)-i-j

• 对于第四区域的 (p,q)

  dp_{i,j}=(\min_{p,q}dp_{p,q}+p-q)-i+j

然后你需要一个：

1. 能够在网格图中加入一些数
2. 查询从 (1,1) 到 (i,j) 的矩形中的最小值

可以使用二维树状数组。

那如何清空呢？

在加入的时候会遍历到一些位置，清空的时候，照着枚举一边，把途径的所有位置全部清空。

复杂度 O(nm\log^2(nm))。

Code

#include<bits/stdc++.h>
#define int long long
#define Pair pair<int,int>
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;
const int MAXN=700+5;
const int inf=1e18;
int n,m,p,a[MAXN][MAXN];
int dp[MAXN][MAXN];
vector<Pair>G[MAXN*MAXN];
inline int dis(Pair a,Pair b){
    return abs(a.first-b.first)+abs(a.second-b.second);
}
#define lb(x) (x&-x)
int tr1[MAXN][MAXN],tr2[MAXN][MAXN],tr3[MAXN][MAXN],tr4[MAXN][MAXN];
#define Up1 for(int x=X;x<=n;x+=lb(x))
#define Down1 for(int x=X;x;x-=lb(x))

#define Up2 for(int y=Y;y<=m;y+=lb(y))
#define Down2 for(int y=Y;y;y-=lb(y))

inline void add1(int X,int Y,int k){Up1 Up2 tr1[x][y]=min(tr1[x][y],k);}
inline int qry1(int X,int Y){int ans=inf;Down1 Down2 ans=min(ans,tr1[x][y]);return ans;}
inline void init1(int X,int Y){Up1 Up2 tr1[x][y]=inf;}

inline void add2(int X,int Y,int k){Up1 Down2 tr2[x][y]=min(tr2[x][y],k);}
inline int qry2(int X,int Y){int ans=inf;Down1 Up2 ans=min(ans,tr2[x][y]);return ans;}
inline void init2(int X,int Y){Up1 Down2 tr2[x][y]=inf;}

inline void add3(int X,int Y,int k){Down1 Down2 tr3[x][y]=min(tr3[x][y],k);}
inline int qry3(int X,int Y){int ans=inf;Up1 Up2 ans=min(ans,tr3[x][y]);return ans;}
inline void init3(int X,int Y){Down1 Down2 tr3[x][y]=inf;}

inline void add4(int X,int Y,int k){Down1 Up2 tr4[x][y]=min(tr4[x][y],k);}
inline int qry4(int X,int Y){int ans=inf;Up1 Down2 ans=min(ans,tr4[x][y]);return ans;}
inline void init4(int X,int Y){Down1 Up2 tr4[x][y]=inf;}
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m>>p;
    G[0].push_back(Pair(1,1));
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        cin>>a[i][j];
        G[a[i][j]].push_back(Pair(i,j));
    }
    mem(tr1,0x3f),mem(tr2,0x3f),mem(tr3,0x3f),mem(tr4,0x3f);
    for(int t=1;t<=p;t++){
        for(auto [p,q]:G[t-1]){
            add1(p,q,dp[p][q]-p-q);
            add2(p,q,dp[p][q]-p+q);
            add3(p,q,dp[p][q]+p+q);
            add4(p,q,dp[p][q]+p-q);
        }
        for(auto [x,y]:G[t]){
            dp[x][y]=min({
                qry1(x,y)+x+y,
                qry2(x,y)+x-y,
                qry3(x,y)-x-y,
                qry4(x,y)-x+y
            });
        }
        for(auto [p,q]:G[t-1]){
            init1(p,q);
            init2(p,q);
            init3(p,q);
            init4(p,q);
        }
    }
    int ans=inf;
    for(auto [x,y]:G[p])ans=min(ans,dp[x][y]);
    cout<<ans<<"\n";
}