U606899 赛博朋克 边缘行者

· · 个人记录

前置算法

二分，动态规划

题目分析

我们先考虑怎么暴力 dp，因为每次只能往右或者往下，那我们定义 dp_{i,j} 表示从 (x_1,y_1) 走到 (i,j) 的最小权值总和，转移如下：

dp_{i,j}=\min(dp_{i-1,j},dp_{i,j-1})+a_{i,j}

通过数据的提示，我们容易想到对角线二分。当 (x_1,y_1) 和 (x_2,y_2) 在对角线同一侧时，就进行暴力 dp，如果在对角线两侧的话，因为从起点到终点一定会经过对角线上的某一个点。那么我们可以枚举对角线上的点，然后计算从起点到这个点，从这个点到终点的最小权值总和，再对所有的对角线上的点求 min 即可。

但是我们会发现这样的复杂度并不对，如果所有点都在对角线的同一侧的话，那么复杂度是 O(q\frac{n^2}{2^2})，会超时。

那么我们可以想到多画几条对角线不就可以了，经过计算，我们最终需要画七条对角线，那么复杂度就是 O(q\frac{n^2}{2^6})，可以通过。

画七条对角线的图大概长这样：

最后我们要对询问离线处理，把经过同一条对角线的询问放在一起，然后一起计算。

细节比较多，题解中讲的不够详细，详细的请看代码。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=210;
const int M=201010;
ll ans[M],sx[M],sy[M],tx[M],ty[M],vis[M];
ll n,m,a[N][N],dp[N][N][N],len[N],xx[N],yy[N],f[N][N];
vector<ll>g[10];
void check(ll s,ll t,ll op,ll lx,ll ly){
    for(int i=s;i<=n;i++){
        for(int j=t;j<=n;j++){
            if(i+j<lx||i+j>ly)continue;
            if(i==s&&j==t)dp[op][i][j]=a[i][j];
            else dp[op][i][j]=min(dp[op][i-1][j],dp[op][i][j-1])+a[i][j];
        }
    }
    for(int i=s;i>=1;i--){
        for(int j=t;j>=1;j--){
            if(i+j<lx||i+j>ly)continue;
            if(i==s&&j==t)dp[op][i][j]=a[i][j];
            else dp[op][i][j]=min(dp[op][i+1][j],dp[op][i][j+1])+a[i][j];
        }
    }
}
ll js(ll op){
    ll x,y,i=0,j=0,tot=0;
    if(op==1)x=0,y=2*n,i=1,j=len[op];
    if(op==2)x=0,y=n+1,i=1,j=len[op];
    if(op==3)x=n,y=2*n,i=len[op]-n+1,j=n;
    if(op==4)x=0,y=n/2,i=1,j=len[op];
    if(op==5)x=n/2,y=n+1,i=1,j=len[op];
    if(op==6)x=n,y=n+n/2+1,i=len[op]-n+1,j=n;
    if(op==7)x=n+n/2,y=2*n,i=len[op]-n+1,j=n;
    while(1){
        if(i>n||j<1)break;
        tot++;
        check(i,j,tot,x,y);
        xx[tot]=i,yy[tot]=j;
        i++,j--;
    }
    return tot;
}
ll baoli(ll sx,ll sy,ll tx,ll ty){
    for(int i=sx-1;i<=tx+1;i++)for(int j=sy-1;j<=ty+1;j++)f[i][j]=1e18;
    for(int i=sx;i<=tx;i++){
        for(int j=sy;j<=ty;j++){
            if(i==sx&&j==sy)f[i][j]=a[i][j]; 
            else f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j];
        }
    }
    return f[tx][ty];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    len[1]=n,len[2]=n/2,len[3]=n+n/2,len[4]=n/4,len[5]=n/2+n/4,len[6]=n+n/4,len[7]=n+n/2+n/4;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
    for(int i=1;i<=m;i++){
        cin>>sx[i]>>tx[i]>>sy[i]>>ty[i];
        for(int j=1;j<=7;j++){
            if(sx[i]+sy[i]<=len[j]+1&&tx[i]+ty[i]>=len[j]+1){
                vis[i]=1;
                g[j].push_back(i);
                break;
            }
        }
    }
    for(int i=1;i<=7;i++){
        if(!g[i].size())continue;
        memset(dp,0x3f,sizeof(dp));
        ll len=js(i);
        for(auto j:g[i]){
            ans[j]=1e18;
            for(int k=1;k<=len;k++){
                ans[j]=min(ans[j],dp[k][sx[j]][sy[j]]+dp[k][tx[j]][ty[j]]-a[xx[k]][yy[k]]);
            }
        }
    }
    for(int i=1;i<=m;i++){
        if(vis[i])continue;
        ans[i]=baoli(sx[i],sy[i],tx[i],ty[i]);
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
    return 0;
}