【题解】洛谷P1514 [NOIP2010TG] 引水入城（DFS+DP）

次元传送门：洛谷P1514

思路

可以证明如果有解 那么每个蓄水池可以覆盖到的干旱区必定是线段

证明：

举个栗子

8 9 8

7 9 7

6 9 6

明显到不了中间的点 如果不是连续的线段 中间肯定有一个点到不了 无解

那么我们就可以从每个开头城市进行DFS 并且同时递归计算每个点可以到达的最左边和最右边

最后进行一个线段覆盖问题解决

注意最左边是取最小值 最右边是取最大值

代码

#include<iostream>

#include<cstring>

#include<queue>

using namespace std;

#define maxn 505

int dx[]={,,,-},

    dy[]={,-,,};

int n,m,ans,sum,num;

int high[maxn][maxn],l[maxn][maxn],r[maxn][maxn];

bool vis[maxn][maxn],k;

void dfs(int x1,int y1)

{

    vis[x1][y1]=;

    for(int i=;i<;i++)//枚举方向

    {

        int x2=x1+dx[i];

        int y2=y1+dy[i];

        if(x2>=&&x2<=n&&y2>=&&y2<=m&&high[x2][y2]<high[x1][y1])//判断条件

        {

            if(!vis[x2][y2]) dfs(x2,y2);//如果下一个点没有被遍历过 进行遍历

            l[x1][y1]=min(l[x1][y1],l[x2][y2]);//递归时计算最右边和最左边

            r[x1][y1]=max(r[x1][y1],r[x2][y2]);

        }

    }

}

int main()

{

    memset(l,0x3f,sizeof(l));//因为取最小值 所以赋值为极大值

    cin>>n>>m;

    for(int i=;i<=m;i++) l[n][i]=r[n][i]=i;//初始化边界（最下面一行）

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++) cin>>high[i][j];

    for(int i=;i<=m;i++)

    {

        if(vis[][i]==)//如果这个城市没有试过且没有被其他蓄水池到达过

        dfs(,i);//进行搜索

    }

    for(int i=;i<=m;i++)//判断是否有解

        if(!vis[n][i])//如果最后一行有一个没有被到达过的点 即无解

        {

            num++;//计算有几个不能到达

            k=;

        }

    if(k)//无解

    {

        cout<<<<endl<<num;

        return ;

    }

    int now=;//线段覆盖

    while(now<=m)//如果当前处在位置小于总长就继续

    {

        int maxr=;//当前区间可以覆盖到的最右边

        for(int i=;i<=m;i++)//枚举区间

            if(l[][i]<=now) maxr=max(maxr,r[][i]);//计算最右边

        sum++;//增加数量

        now=maxr+;//计算最左边

    }

    cout<<<<endl<<sum;

}