Mas's Blog
Masellum 的生活日志
[NOIP2010] 引水入城

题目

题目链接

题目描述

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

样例图片
样例图片

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

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

输入输出格式

输入格式:

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

输出格式:

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

说明

数据范围
数据范围

题解

经过观察思考发现,如果第 mm 行的所有点都能够被搜索到,那么从第 11 行的任何一个点出发所能搜索到的第 mm 行的格子一定是连续的;否则第 mm 行一定会有格子搜不到。通过记忆化搜索,搜索出从第 11 行的每个点可以覆盖的区间,同时统计搜到的第 mm 行的格子的个数,如果搜完以后发现不到 mm 个那么第一问的答案是 00

在处理出第1行的每个格子可以搜到的区间之后,问题转化成“给定一些线段,用最少数量的线段覆盖整个区间”。我们记录下当前已经覆盖到的区间的右端点 rr,每次都去找左端点在 rr 左侧的右端点最靠右的线段去覆盖,然后更新 rr 与已选择的线段数量。(这样的复杂度上限是 O(m2)O(m^2) 的,感觉上似乎可以优化但是也能过就算了(。

代码

Finita la comedia.