题解：P1514 [NOIP 2010 提高组] 引水入城

· · 题解

题目大意

有一个 n\times m 的格子，第一行可以建造蓄水池，最后一行是沙漠，询问最少建造多少个蓄水池可以滋润到所有的沙漠土地，如果不能滋润到所有的沙漠土地，就输出有多少个沙漠土地不能被灌溉。

大体思路

just 避雷

这里有个比较典型的错误思路，注意不要掉进坑里，就是不要从蓄水池行贪心找最大值，这看上去很对，但是我们一旦找一个例子你就傻了。

我们其实选择 6 这个点就可以灌溉所有的沙漠块，但是选择 7 只能灌溉一个，原因是被相同点数的块卡住了。

这种方式或许在无论什么块都需要滋润的题中有效，但在这个题中是不行的。

正确思路

首先我们先从每一个蓄水区开始深搜，由于题目数据比较小，我们无需进行一些记忆化的操作，用 sf 数组记录每一个沙漠块能否被灌溉到，用 edge 二维数组记录当前蓄水池能否灌溉到对应沙漠块（像一条条边一样的，能否连接）。当然了，我们这里还可以记录左端点右端点来优化，但还是由于题目数据较小，我们可以朴素的写连边的方式。

这样 DFS 后，我们就判断能不能全部滋润，如果不能就赶紧给出不能的答案，前面我们已经处理过了。

观察可以得到（看到题解区都有所证明，我就不进行证明了），每一个蓄水池在沙漠块的灌溉是一个连通块，没错是连续的，这样引诱着我们想到一个做法——从沙漠块开始贪心。

我的方法是，先找到灌溉最长的从第一个沙漠块开始的蓄水池，并选择他，记录他能滋润到的最远沙漠块，然后进入循环。

在循环中，我们从能滋润到的最远沙漠块的后一个块从后向前开始询问，选择它能够滋润到的最远沙漠块是哪里，记录最大值，并选择，就这样循环一直到最后一个块被滋润。

这里就有各种实现方式可以选择，我比较喜欢朴素的实现方式，如果实在想不到实现方式的，可以看下面的代码及每一步的优化建议。

Code

题解区题解各有所长，方法也不尽相同，为了不显得那么平平无奇，我的长处就是朴素且详细注释的代码！力求每一个新手都能看得懂。

（以及优化建议）

#include<bits/stdc++.h>
using namespace std;
long long read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
void write(long long x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
    return ;
}
int n,m;
int tu[505][505];
bool vis[505][505];//当前蓄水池的遍历有没有走过这个点 
bool sf[505];//标记这个点是否能被滋润
bool edge[505][505];//第一维是蓄水池，第二维是沙漠，连接表示该蓄水池能滋润对应沙漠 
int xx;
void dfs(int x,int y){//深搜找每个沙漠地带会被哪几个蓄水厂滋润到 
    vis[x][y]=1;//打上标记，这一次遍历中不会再来了 
    if(x==n){
        sf[y]=1;
        edge[xx][y]=1;
    }

    if(x-1>=1&&y>=1&&!vis[x-1][y]&&tu[x-1][y]<tu[x][y]){//可以向四个方向搜索 
        dfs(x-1,y);
    }
    if(x>=1&&y-1>=1&&!vis[x][y-1]&&tu[x][y-1]<tu[x][y]){
        dfs(x,y-1);
    }
    if(x>=1&&y+1<=m&&!vis[x][y+1]&&tu[x][y+1]<tu[x][y]){
        dfs(x,y+1);
    }
    if(x+1<=n&&y>=1&&!vis[x+1][y]&&tu[x+1][y]<tu[x][y]){
        dfs(x+1,y);
    }
}
void pans(){//找一片净土来累加答案吧（全写循环里真的太丑了） 
    int sum=0;
    for(int i=1;i<=m;i++){
        if(!sf[i]){
            sum++;
        }
    }
    write(sum);
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            tu[i][j]=read();
        }
    }
    for(int i=1;i<=m;i++){
        xx=i;
        dfs(1,i);//时间给的足，我们并不需要记忆化 
        for(int j=1;j<=n;j++){
            for(int k=1;k<=m;k++){
                vis[j][k]=0;//下一次遍历我们仍需记录，所以还得去 
            }
        }
    }
    for(int i=1;i<=m;i++){
        if(!sf[i]){
            puts("0");
            pans();//不可以全部滋润就直接输出答案（译为puts ans(?)） ，可以优化 
            return 0;
        }
    }
    xx=1;//没用的变量重复使用一下吧，记录一下现在在的点坐标
    for(int v=1;v<=m;v++){//时间给的足，不需要提前记录 
        if(!edge[v][1]){
            continue ;
        }
        for(int i=2;i<=m;i++){
            if(edge[v][i]){
                xx=max(xx,i);
            }
            else{
                break ;
            }
        }
    }
    int ans=1;//我们已经选了上一个了，ans初始化为 1 
    while(xx<m){//时间给的足，不需要提前预处理左端点和右端点 
        int xxnext=xx;
        for(int i=xx+1;i>=1;i--){
            for(int k=1;k<=m;k++){//暴力的询问每一个蓄水池是否能到达当前沙漠块（可以优化） 
                if(edge[k][i]){
                    for(int j=xxnext+1;j<=m;j++){//我们优化掉无法更新答案的情况 
                        if(edge[k][j]){
                            xxnext=j;//我们保证小于xxnext的j进不去循环，就能优化更新 
                        }
                        else{
                            break ;
                        }
                    }           
                }
            }
        }
        xx=xxnext;//前进！ 
        ans++; 
    }//如果已经可以灌溉到最后一寸土地了，那么就跳出循环 
    puts("1");
    write(ans);
    return 0;//程序中所谓“时间给的足”都是可以优化的点，比较简单，这里不在过多说明，本道题也不必要 
}

The End!