CF677D Vanya and Treasure

做法

一道简单的 dp 题。

我们设 S_{p} 为数字为 p 的位置所构成的集合，f_i 为解开位置 i 上的锁所需的最小步数。
转移是显然的，对于一个位置 i\in S_{p}，f_i=\min_{j\in S_{p-1}}\{f_{j}+\lvert x_i-x_j \rvert+\lvert y_i-y_j \rvert \}。
暴力转移会被卡到 O(n^2m^2)，考虑如何快速求出 f_i。
不难想到拆绝对值，我们分类讨论，发现有四种情况：

对这四种情况分别开一个二维树状数组即可做到快速转移。
时间复杂度为 O(n^2\log^2 n)（这里认为 n,m 同阶），可以通过此题。

代码

#include <bits/stdc++.h>
using namespace std;
namespace fisher{
#define int long long
#define per(i,a,b) for(int i=(a);i<=(b);i++)
#define rep(i,b,a) for(int i=(b);i>=(a);i--)
#define pb push_back
#define epb emplace_back
#define all(x,l,r) &(x)[l],&(x)[r]+1
#define cto const auto
#define lowbit(x) ((x)&(-(x)))
template <class T> bool chkmn(T &x,T y){return x>y?(x=y,1):0;}
template <class T> bool chkmx(T &x,T y){return x<y?(x=y,1):0;}
char buf[1<<20],*p1,*p2;
#define getchar() ((p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2))?0:*p1++)
int read() {
    char ch=getchar();int x=0,f=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
#undef getchar
bool mbs;void cntime();
const int N=5e5+5,M=705,inf=1e18;
int n,m,k,ans=inf,f[N];
vector <array<int,2>> p[N];
struct BIT{
    int t[M][M];
    void init(){
        per(i,1,n) per(j,1,m) t[i][j]=inf;
    }
    void update(int x,int y,int k){
        for(int i=x;i<=n;i+=lowbit(i))
            for(int j=y;j<=m;j+=lowbit(j))
                chkmn(t[i][j],k);
    }
    void clear(int x,int y){
        for(int i=x;i<=n;i+=lowbit(i))
            for(int j=y;j<=m;j+=lowbit(j))
                t[i][j]=inf;
    }
    int query(int x,int y){
        int res=inf;
        for(int i=x;i;i-=lowbit(i))
            for(int j=y;j;j-=lowbit(j))
                chkmn(res,t[i][j]);
        return res;
    }
}t[4];
#define gid(x,y) (((x-1)*m+(y)))
#define fpx (n-x+1)
#define fpy (m-y+1)
#define dis(x1,y1,x2,y2) (abs(x1-x2)+abs(y1-y2))
void solve(int i){
    for(auto id:p[i-1]){
        int x=id[0],y=id[1],pl=gid(x,y);
        t[0].update(x,y,f[pl]-x-y);
        t[1].update(x,fpy,f[pl]-x+y);
        t[2].update(fpx,y,f[pl]+x-y);
        t[3].update(fpx,fpy,f[pl]+x+y);
    }
    for(auto id:p[i]){
        int x=id[0],y=id[1],pl=gid(x,y);
        chkmn(f[pl],t[0].query(x,y)+x+y);
        chkmn(f[pl],t[1].query(x,fpy)+x-y);
        chkmn(f[pl],t[2].query(fpx,y)-x+y);
        chkmn(f[pl],t[3].query(fpx,fpy)-x-y);
    }
    for(auto id:p[i-1]){
        int x=id[0],y=id[1];
        t[0].clear(x,y);
        t[1].clear(x,fpy);
        t[2].clear(fpx,y);
        t[3].clear(fpx,fpy);
    }
}
void main(){
    n=read();m=read();k=read();
    per(i,1,n) per(j,1,m)
        p[read()].pb({i,j});
    fill(all(f,1,n*m),inf);
    per(i,0,3) t[i].init();
    for(auto id:p[1])
        f[gid(id[0],id[1])]=dis(1,1,id[0],id[1]);
    per(i,2,k) solve(i);
    for(auto id:p[k]) chkmn(ans,f[gid(id[0],id[1])]);
    printf("%lld\n",ans);
    return cntime();
}
bool mbe;void cntime(){
    cerr<<"Time: "<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n";
    cerr<<"Memory: "<<abs(&mbe-&mbs)/1024./1024.<<" MB\n";
}}
signed main(){
    fisher::main();
    return 0;
}