记忆化搜索——P1514 [NOIP2010 提高组] 引水入城

传送门: [NOIP2010 提高组] 引水入城 - 洛谷

思路:

问题有两种情况能和不能

从最上面的一行开始逐个记忆化搜索看最后能不能覆盖完最下面一行的所有点如果存在不能覆盖的点就统计个数

如果不存在的话就要统计最少可以只修建多少个蓄水厂就能覆盖完干旱区的所有城市而这个需要

统计每一个点所能扩展到的最左边的城市以及最右边的城市最上面一排的城市就可以对应一个个区间问题变成了用最少的区间覆盖给定区域范围。

代码: 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=510;
int n,m;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int l[N][N],r[N][N];
int d[N][N];
bool st[N][N];
void dfs(int x,int y)
{
    st[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<1||yy>m||xx>n||yy<1||d[xx][yy]>=d[x][y])continue;

        if(!st[xx][yy]) dfs(xx,yy);
        l[x][y]=min(l[x][y],l[xx][yy]);
        r[x][y]=max(r[x][y],r[xx][yy]);
    }
}
signed main()
{
    memset(l,0x3f,sizeof l);
    scanf("%lld%lld",&n,&m);

    for (int i=1;i<=m;i++)
        l[n][i]=r[n][i]=i;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        scanf("%lld",&d[i][j]);

    for(int i=1;i<=m;i++)
        if(!st[1][i]) dfs(1,i);

    bool flag=false;
    int cnt=0;

    for(int i=1;i<=m;i++)
    {
        if(!st[n][i])
        {
            flag=true;
            cnt++;
        }
    }
    if(flag)
    {
        puts("0");
        printf("%lld",cnt);
        return 0;
    }

    int left=1;
    while(left<=m)
    {
        int maxr=0;
        for(int i=1;i<=m;i++)
            if(l[1][i]<=left)
            maxr=max(maxr,r[1][i]);
        cnt++;
        left=maxr+1;
    }
    puts("1");
    printf("%lld",cnt);

	return 0;
}