NOIP2010提高组T4：引水入城

题目链接

[NOIP2010 提高组] 引水入城

题目描述

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

1
1

样例 #2

样例输入 #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 个测试数据，每个数据的范围如下表所示：

测试数据编号	能否满足要求	$N\le$	$M\le$
1	不能	$10$	$10$
2	不能	$100$	$100$
3	不能	$500$	$500$
4	能	$1$	$10$
5	能	$10$	$10$
6	能	$100$	$20$
7	能	$100$	$50$
8	能	$100$	$100$
9	能	$200$	$200$
10	能	$500$	$500$

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

算法思想

分析测试样例可以发现，在第 $1$ 行的城市建造蓄水厂，可以输送到第$N$行一段连续的区间中，如下图所示：

如果能求出第$1$行每个格子能够“覆盖”的最大范围$[L,R]$，那么这个问题就变成用$M$个闭区间，覆盖一个线段区间$[1,m]$的区间覆盖问题。

例如：

• 测试样例1中，$8$能够覆盖的范围是$[1,5]$，只用$1$个区间就能完全覆盖。
• 测试样例2中，需要用$3$个区间才能完全覆盖。

如何求每个格子能够“覆盖”的最大范围呢？由于每个格子只能向其相邻城市从高处向低处输送，那么其转移过程不可能有环，即存在拓扑序列，可以用动态规划的思想来解决。

状态表示

$f[x][y]$表示第$x$行第$y$列的格子能够覆盖第$N$行的最大区间$[L,R]$

最终，$f[1][i]$表示在第$1$行第$i$列建造蓄水厂能够在第$N$行覆盖的最大区间。

状态计算

要在$1$行的城市建造蓄水厂，就要枚举第$1$行的每个格子，计算状态。由于是在方阵中进行状态转移，可以通过记忆化搜索的方式实现。

计算第$x$行，第$y$列的状态

• 枚举其相邻的$4$个格子，不妨设为$[a,b]$；
• 如果能够从$[x,y]$转移到$[a,b]$，那么递归计算$f[a][b]$
• $f[x][y].L=min(f[x][y].L,f[a][b].L)$，$f[x][y].R=max(f[x][y].R,f[a][b].R)$

初始状态

• 由于使用记忆化搜索实现，将$f[x][y]$初始状态设为$[?1,?1]$表示状态还没有计算过。
• 当计算到第$N$行时，$f[x][y]$的初始值应设为$[y,y]$，表示至少能够覆盖当前格子。

完成状态计算后，如果$f[N][i]$为$[?1,?1]$表示第$N$行第$i$列无法被覆盖，即不可能建有水利设施。

时间复杂度

• 由于使用了记忆化搜索，每个格子只会搜索一次，因此时间复杂度为$O(n\times m)$
• 区间覆盖问题的时间复杂度与区间数量$m$相关，时间复杂度为$O(m)$

代码实现

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 510;
typedef pair<int, int> PII;
PII f[N][N];
int n, m, h[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void dfs(int x, int y)
{
    //状态已经计算过了
    if(f[x][y].first != -1) return ;
    f[x][y].first = N; //求最小值
    if(x == n) f[x][y] = {y, y}; //计算到第n行时初始状态
    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) continue;
        if(h[a][b] >= h[x][y]) continue;
        dfs(a, b); //递归计算
        f[x][y].first = min(f[x][y].first, f[a][b].first);
        f[x][y].second = max(f[x][y].second, f[a][b].second);
    }
}
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);
    //枚举第1行每一列进行状态计算
    for(int i = 1; i <= m; i ++) dfs(1, i);
    //计算不可能建有水利设施的城市数目
    int res = 0;
    for(int i = 1; i <= m; i ++)
        if(f[n][i].first == -1) res ++;
    if(res) printf("0\n%d", res);
    else
    {
        //统计封闭区间
        vector<PII> segs;
        for(int i = 1; i <= m; i ++)
            segs.push_back(f[1][i]);
        //排序，求最小区间覆盖
        sort(segs.begin(), segs.end());
        int ans = 0, L = 1; //L表示要覆盖的区间左端点
        for(int i = 0; i < m;)
        {
            int R = 0; //R表示能够覆盖L的区间的最大右端点
            while(i < m && segs[i].first <= L)
                R = max(R, segs[i ++].second);
            ans ++;
            if(R >= m) break; //完成覆盖            
            L = R + 1; //下次要覆盖的最左边位置
        }
        printf("1\n%d", ans);
    }
}