题解 | #北水南调（NtoS）#

南水北调(记忆化搜索 + 区间覆盖)

1.可以证明如果干旱区域每个城市都能被覆盖的话，每个蓄水厂所能灌溉的干旱区域一定是连续的

反证法：

如果存在不连续的城市，那么容易得知不连续的城市中间的城市一定不能被其他所有的蓄水厂灌溉到，所以如果能满足要求的话，每个蓄水厂所能灌溉的干旱区域一定是连续的

2.l[i][j] r[i][j] 分别表示从第i行第j列的城市出发点水在干旱区所能覆盖到的左边界和右边界 两个数组可以用 记忆化搜索 得到

3.通过区间覆盖得到答案 code"

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define x first
#define y second
typedef pair<int,int>PII;
const int N=510;
int n,m,h[N][N],dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
PII f[N][N];
vector<PII>segs;
inline void dp(int x,int y){
    auto &p=f[x][y];
    if(p.x!=-1) return  ;
    p.x=N;
    if(x==n) p={y,y};
    for(int i=0;i<4;i++){
        int a=x+dx[i],b=y+dy[i];
        if(a>=1&&a<=n&&b>=1&&b<=m&&h[a][b]<h[x][y]){
            dp(a,b);
            p.x=min(p.x,f[a][b].x);
            p.y=max(p.y,f[a][b].y);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>h[i][j];
        }
    }
    memset(f,-1,sizeof f);
    for(int i=1;i<=m;i++) dp(1,i);
    int cnt=0;
    for(int i=1;i<=m;i++){
        if(f[n][i].x==-1){
            cnt++;
        }
    }
    if(cnt){
        cout<<0<<endl<<cnt<<endl;
    }else{
        cout<<1<<endl;
        for(int i=1;i<=m;i++){
            segs.push_back(f[1][i]);
        }
        sort(segs.begin(),segs.end());
        int res=0;
        for(int i=0,strat=1;i<m;){
            int maxz=0;
            while(i<m&&segs[i].x<=strat){
                maxz=max(maxz,segs[i].y);
                i++;
            }
            res++;
            if(maxz>=m) break;
            strat=maxz+1;
        }
        cout<<res<<endl;
    }
    return 0;
}