洛谷 P1514 NOIp2010提高组 引水入城 题解【记忆化搜索】【贪心】【状态压缩】

点击量：166

    一个看上去很DP的题怎么就可以贪心呢

目录

题目描述

在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个N行×M列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。

为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。

 

因此，只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第N行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。

 

输入输出格式

输入格式：

每行两个数，之间用一个空格隔开。输入的第一行是两个正整数N,M，表示矩形的规模。接下来N行，每行M个正整数，依次代表每座城市的海拔高度。

 

输出格式：

两行。如果能满足要求，输出的第一行是整数1，第二行是一个整数，代表最少建造几个蓄水厂；如果不能满足要求，输出的第一行是整数0，第二行是一个整数，代表有几座干旱区中的城市不可能建有水利设施。

输入输出样例

输入样例#1：

2 5
9 1 5 4 3
8 7 6 1 2

输出样例#1：

1
1

输入样例#2：

3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2

输出样例#2：

1
3

说明

【样例1说明】

只需要在海拔为9的那座城市中建造蓄水厂，即可满足要求。

 

【样例2说明】

上图中，在3个粗线框出的城市中建造蓄水厂，可以满足要求。以这3个蓄水厂为源头在干旱区中建造的输水站分别用3 种颜色标出。当然，建造方法可能不唯一。

 

【数据范围】

本题共有10个测试数据，每个数据的范围如下表所示：

对于所有的10个数据，每座城市的海拔高度都不超过$ 10^6$。

题解：

    首先我们要通过题目意思并手玩数据得出一个重要的结论，从第一行一个方格出发，如果方案合法，那么流到最后一行所覆盖的一定是一个连续的区间。我们看这样一个图：

    如果这张图代表了在S点建一个水厂水的流动方向。而我们看到最后一行第4个点，它的所有来路都被访问过，可是就是进不来这里，因此得出结论，这张图上的最后一行第4个点是无论如何都会干旱的。因此在所有水厂建完之后，没有被水覆盖的点就会干旱，统计这样的点的个数。

    在解决了如何判断有合法方案的问题后，我们来找最后一行所有点都被覆盖的最优解情况。既然每个点引出来的水流都是一段区间，那我们就可以把这个问题转化为“最优区间覆盖”，也就是用最少的区间覆盖整个最后一行。这样我们贪心地在左端点在当前已经覆盖过的部分或该部分右侧一格的区间中找出右端点最大的选上，也就尽可能扩展了区间。这样当第一次触碰到第m列时，答案就是当前计数个数。

    那么如何找出一个点有水会使哪些点有水呢？我们总是只关心最后一行，所以我们对每个点使用一个bitset状压，当作一个可以进行位运算的bool数组来用，如果找到四周的一个点比自己小，就去转移它的状态，也就是它能覆盖到最后一行的哪些点，接着递归搜索。需要注意的是，搜索到最后一行也不一定就停止了，因为水可以往上流，也可以横着流，直到找到一个盆地/谷地才可能停止。注意要初始化最后一行的每个点可以覆盖自己。

Code：

#include<cstdio>
#include<bitset>
#include<cstring>
#include<algorithm>
using std::bitset;
bitset<510> b[510][510];//可以到达的点
int a[510][510];
bool used[510][510];
int n,m;
void dfs(int x,int y)
{
    if(y>1&&a[x][y-1]<a[x][y])
    {
        if(!used[x][y-1])
            dfs(x,y-1);
        b[x][y]|=b[x][y-1];
    }
    if(y<m&&a[x][y+1]<a[x][y])
    {
        if(!used[x][y+1])
            dfs(x,y+1);
        b[x][y]|=b[x][y+1];
    }
    if(x<n&&a[x+1][y]<a[x][y])
    {
        if(!used[x+1][y])
            dfs(x+1,y);
        b[x][y]|=b[x+1][y];
    }
    if(x>1&&a[x-1][y]<a[x][y])
    {
        if(!used[x-1][y])
            dfs(x-1,y);
        b[x][y]|=b[x-1][y];
    }
    used[x][y]=1;//搜完了，可以转移了
    return;
}
struct seg
{
    int l,r;
    friend bool operator <(seg a,seg b)
    {
        return a.l<b.l;
    }
}s[510];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=m;i++)
        b[n][i][i]=1;
    int flag=0;
    for(int i=1;i<=m;i++)
    {
        int tmp=0;
        dfs(1,i);
        for(int j=1;j<=m;j++)
        {
            if(b[1][i][j]==0&&b[1][i][j-1]==1)
            {
                tmp=1;
                s[i].r=j-1;
            }

            if(b[1][i][j]==1&&b[1][i][j-1]==0)
                s[i].l=j;
        }
        if(s[i].r==0&&b[1][i][m])
            s[i].r=m;
    }
    bitset<510> tot;
    for(int i=1;i<=m;i++)
        tot|=b[1][i];
    for(int i=1;i<=m;i++)
        if(tot[i]==0)//判断全部融合起来有没有不能访问的
            flag++;
    if(flag)
    {
        printf("0\n%d\n",flag);
        return 0;
    }
    std::sort(s+1,s+1+m);
    int r=1,cur=1,cnt=0;
    while(r<=m)
    {
        ++cnt;
        int mx=0;
        for(;s[cur].l<=r&&cur<=m;cur++)//注意要<=m，不然会出错
            mx=mx>s[cur].r?mx:s[cur].r;
        r=mx+1;
    }
    printf("1\n%d\n",cnt);
    return 0;
}