题解：P6797 「StOI-2」不朽的逃亡者

· · 题解

题目分析

设 g_{i,j} 表示走到 (i,j) 前，还没有计算 (i,j) 危险值时的最小代价。

不选择任何人时，就是普通的网格 DP：

g_{i+1,j}\gets\min(g_{i+1,j},g_{i,j}+d_{i,j}), g_{i,j+1}\gets\min(g_{i,j+1},g_{i,j}+d_{i,j}).

接下来考虑加入一个人的贡献，假设这个人保护的矩形为 [a,b]\times[c,d]。

因为矩形内部的危险值全部变成 0，所以只需要考虑从某个位置进入矩形，然后从矩形的 下边界或右边界 离开。

假设从 (b+1,y) 离开，能够免费走到这里的起点为矩形中满足列坐标不超过 y 的位置，因此：

f_{b+1,y}\gets \min\left( f_{b+1,y}, \min_{\substack{a\le x\le b\\c\le z\le y}}g_{x,z} \right).

枚举 y 时维护前缀最小值即可。同理对于 (x,d+1)：

f_{x,d+1}\gets \min\left( f_{x,d+1}, \min_{\substack{a\le z\le x\\c\le y\le d}}g_{z,y} \right).

也是维护一个前缀最小值。

需要快速求一整列或一整行上的区间最小值，分别对每一列和每一行建立线段树。

由于每个人对应的查询区间始终不变，可以预处理区间在线段树上被拆成了哪些节点，之后直接访问这些节点的最小值。

处理完所有矩形后，再进行一次普通网格 DP，使当前位置继续向右、向下扩展。

重复上述过程至多 \min(k,w) 次。

因为每轮都有 f\gets g，所以第 i 轮表示的是 至多选择 i 个人 的最优答案，而不是恰好选择 i 个人。

认为 n,m 同阶，总时间复杂度为 O(\min(k,w)n^3\log n)，空间复杂度为 O(n^2+k\log n)。

能用 O(n)-O(1) RMQ 做到 O(n^3)。

参考代码

:::info[Code]

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pb emplace_back
const int N=205,inf=1e18;
int n,m,k,w,a[N][N],f[N][N],g[N][N];
struct rect{int ax,bx,ay,by;}q[N];
vector<int>seg,C[N],R[N];
struct Tree{
    int t[N][N<<2],s[N][N<<2];
    #define lson l,mid,p<<1
    #define rson mid+1,r,p<<1|1
    #define mid ((l+r)>>1)
    inline void buildC(int y,int l,int r,int p=1){
        if(l==r){t[y][p]=g[l][y];return;}
        buildC(y,lson),buildC(y,rson);
        t[y][p]=min(t[y][p<<1],t[y][p<<1|1]);
    }
    inline void buildR(int x,int l,int r,int p=1){
        if(l==r){s[x][p]=g[x][l];return;}
        buildR(x,lson),buildR(x,rson);
        s[x][p]=min(s[x][p<<1],s[x][p<<1|1]);
    }
    inline void build(){
        for(int y=1;y<=m;++y)buildC(y,1,n);
        for(int x=1;x<=n;++x)buildR(x,1,m);
    }
    inline void queryC(int ql,int qr,int l=1,int r=n,int p=1){
        if(ql<=l&&r<=qr){seg.pb(p);return;}
        if(ql<=mid)queryC(ql,qr,lson);
        if(qr>mid) queryC(ql,qr,rson);
    }
    inline void queryR(int ql,int qr,int l=1,int r=m,int p=1){
        if(ql<=l&&r<=qr){seg.pb(p);return;}
        if(ql<=mid)queryR(ql,qr,lson);
        if(qr>mid) queryR(ql,qr,rson);
    }
}T;
inline void solve(int dp[][N]){
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+a[i][j]);
            dp[i][j+1]=min(dp[i][j+1],dp[i][j]+a[i][j]);
        }
}
inline void OIer_WiFi(){
    scanf("%lld%lld%lld%lld",&n,&m,&k,&w);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%lld",&a[i][j]);

    for(int i=1;i<=k;++i){
        auto &[ax,bx,ay,by]=q[i];
        scanf("%lld%lld%lld%lld",&ax,&bx,&ay,&by);
        seg.clear(),T.queryC(ax,bx),C[i]=seg;
        seg.clear(),T.queryR(ay,by),R[i]=seg;
    }
    memset(g,0x3f,sizeof g);
    g[1][1]=0,solve(g);
    for(int i=1;i<=min(k,w);++i){
        T.build(),memcpy(f,g,sizeof f);
        for(int j=1;j<=k;++j){
            auto [ax,bx,ay,by]=q[j];
            int cur=inf;
            for(int y=ay;y<=by;++y){
                for(int p:C[j]) cur=min(cur,T.t[y][p]);
                f[bx+1][y]=min(f[bx+1][y],cur);
            }
            cur=inf;
            for(int x=ax;x<=bx;++x){
                for(int p:R[j]) cur=min(cur,T.s[x][p]);
                f[x][by+1]=min(f[x][by+1],cur);
            }
        } solve(f);
        if(!memcmp(f,g,sizeof f))break;
        memcpy(g,f,sizeof g);
    }
    printf("%lld",min(g[n+1][m],g[n][m+1]));
}
signed main(){OIer_WiFi();}