CF677D Vanya and Treasure

这题纯大力搞过去的，没用到啥技巧，后面看了下别人的做法发现还是很有意思的

我的做法就很粗暴，考虑令\(f_{i,j}\)表示走到\((i,j)\)的最短路，转移的话不难发现是个分层图DP

但是有一个显然的问题是当相邻两层间的点数很多时，暴力做的话会退化成\(O(n^2\times m^2)\)，因此需要优化

像这种绝对值的式子一眼拆绝对值，不妨根据转移位置相对于现在位置的方向分四种情况讨论，那么对于每个点的转移相当于一个矩阵取\(\min\)的操作

可以直接用树套树做到\(O(nm\times\log (nm))\)，但这题数据范围不大，因此可以每行开树状数组做到\(O(n^2m\times \log m)\)，这样代码也比较好写

而高妙一点的做法是利用根号分治，当相邻两层的点数乘积比较小时就暴力转移，否则可以跑一个\(O(nm)\)的多源最短路，这样平衡过后总复杂度就是\(O(nm\times \sqrt {nm})\)的了

代码就放我写的那种做法了

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=305,INF=1e9;
int n,m,p,a[N][N],f[N][N]; vector <pi> pos[N*N];
#define lowbit(x) (x&-x)
class Tree_Array1
{
	private:
		int lim,mi[N];
	public:
		inline void init(void)
		{
			for (RI i=0;i<=m;++i) mi[i]=INF;
		}
		inline void add(RI x,CI y)
		{
			for (;x<=m;x+=lowbit(x)) mi[x]=min(mi[x],y);
		}
		inline void reset(RI x)
		{
			for (;x<=m;x+=lowbit(x)) mi[x]=INF;
		}
		inline int get(RI x,int ret=INF)
		{
			for (;x;x-=lowbit(x)) ret=min(ret,mi[x]); return ret;
		}
}A[N],B[N];
class Tree_Array2
{
	private:
		int mi[N];
	public:
		inline void init(void)
		{
			for (RI i=0;i<=m;++i) mi[i]=INF;
		}
		inline void add(RI x,CI y)
		{
			for (;x;x-=lowbit(x)) mi[x]=min(mi[x],y);
		}
		inline void reset(RI x)
		{
			for (;x;x-=lowbit(x)) mi[x]=INF;
		}
		inline int get(RI x,int ret=INF)
		{
			for (;x<=m;x+=lowbit(x)) ret=min(ret,mi[x]); return ret;
		}
}C[N],D[N];
#undef lowbit
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d%d",&n,&m,&p),i=1;i<=n;++i)
	for (j=1;j<=m;++j) scanf("%d",&a[i][j]),pos[a[i][j]].push_back(pi(i,j));
	for (i=1;i<=n;++i) A[i].init(),B[i].init(),C[i].init(),D[i].init();
	for (pos[0].push_back(pi(1,1)),i=1;i<=p;++i)
	{
		for (auto [x,y]:pos[i-1])
		A[x].add(y,-x-y+f[x][y]),B[x].add(y,x-y+f[x][y]),C[x].add(y,y-x+f[x][y]),D[x].add(y,x+y+f[x][y]);
		for (auto [x,y]:pos[i])
		{
			f[x][y]=INF; for (j=1;j<=x;++j)	f[x][y]=min(f[x][y],min(x+y+A[j].get(y),x-y+C[j].get(y)));
			for (j=x;j<=n;++j) f[x][y]=min(f[x][y],min(y-x+B[j].get(y),-x-y+D[j].get(y+1)));
		}
		for (auto [x,y]:pos[i-1])
		A[x].reset(y),B[x].reset(y),C[x].reset(y),D[x].reset(y);
	}
	auto [x,y]=pos[p][0]; printf("%d",f[x][y]);
	return 0;
}