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

【输入样例2】

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

输出样例#1:

【输出样例1】

1
1

【输出样例2】

1
3

说明

【样例1 说明】

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

【样例2 说明】

上图中,在3 个粗线框出的城市中建造蓄水厂,可以满足要求。以这3 个蓄水厂为源头

在干旱区中建造的输水站分别用3 种颜色标出。当然,建造方法可能不唯一。

【数据范围】

题目分析

一上来读题让人很摸不着头脑,毕竟蓄水厂输水站什么的长的忒像,而且即使读懂题后,这个模型也不是太好建,可以意识到是个动态规划,但是怎么定义状态,以及转移方程也不是十分直观,我并没有用DP,而是在后边用了个贪心,其实差不多吧。
首先考虑无解的情况,如果无解的话,那么一定在最下边存在一个无论在那里建水厂都无法使它得到水的点。那就好办了,我们可以对于在每一个点建水库的情况进行搜索,最好使用BFS,否则会有爆栈的危险。全部搜索完后,如果存在没有被遍历到的最后一行的点,那么就是无解的情况,统计一下输出就好。如果有解,那么我们就要考虑如何安排水厂是最少的。首先我们想,在第一行的某一个点建水厂,对最后一行的影响一定是一个连续的区间,因为如果存在中间分叉而导致区间不连续的情况,那么中间断掉的那些点就相当于被周围的比他低的点隔离,也就不存在其他的点可以更新它,就是无解的情况了。我们可以借助刚才的BFS,统计出在每一个点建造水厂可以影响到的最左边和最右边的点,既然影响是连续的,那么l,r之间一定是一整个区间。这样问题就转化成了区间覆盖问题,用最少的区间来覆盖整个线段。

然后当你高高兴兴的去交代码的时候,发现你T了一组,怎么回事。
这就说明你的代码出现了冗余的情况,这个看似没毛病的代码怎么会冗余呢?

你再仔细看一下又会发现,当一个点的两边存在一个比他高的点时,这个点就已经被遍历过了,也就是说他的影响区间被包含在了他旁边那个比他高的点的影响区间之内。这是在搜一遍他是没有任何必要的,加上这个重要的剪枝,你的代码就AC了!

恩就是这样,让我们上代码。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <queue>
# define R register
# define LL long long

using namespace std;

int n,m,h[510][510],tot,ans,q[250100][2];

int v[510][510];
struct pp{
int l,r;
pp(){l = 2147483647,r = 0;}//构造函数付初值
}tt[510];

inline void in(R int &a){
R char c = getchar();R int x = 0,f = 1;
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = (x<<1)+(x<<3)+c-'0',c = getchar();
a = x*f;
}

inline bool cmp(pp a,pp b){return a.l < b.l;}

inline int bfs(R int t){
R int head = 0,tail = 0;
q[++tail][0] = 1,q[tail][1] = t;
v[1][t] = t;//直接将标记记为源头的横坐标,避免每次memset。
while(head < tail){
R int x = q[++head][0],y = q[head][1];
if(x==n) tt[t].l = min(tt[t].l,y),tt[t].r = max(tt[t].r,y);
if(x+1<=n&&v[x+1][y]!=t&&h[x+1][y]<h[x][y]) v[x+1][y] = t,q[++tail][0] = x+1,q[tail][1] = y;//一定要在里打标记,不然会死的很惨。
if(x-1>=1&&v[x-1][y]!=t&&h[x-1][y]<h[x][y]) v[x-1][y] = t,q[++tail][0] = x-1,q[tail][1] = y;
if(y+1<=m&&v[x][y+1]!=t&&h[x][y+1]<h[x][y]) v[x][y+1] = t,q[++tail][0] = x,q[tail][1] = y+1;
if(y-1>=1&&v[x][y-1]!=t&&h[x][y-1]<h[x][y]) v[x][y-1] = t,q[++tail][0] = x,q[tail][1] = y-1;
}
}

int yg(){
in(n),in(m);
for(R int i=1; i<=n; ++i)
for(R int j=1; j<=m; ++j)
in(h[i][j]);
for(R int i=1; i<=m; ++i) if(h[1][i-1] <= h[1][i]&&h[1][i+1] <= h[1][i]) bfs(i);//重要的剪枝
for(R int i=1; i<=m; ++i) if(!v[n][i]) tot++;
if(tot) {printf("0\n%d",tot); exit(0);}//误解直接输出答案退出。
sort(tt+1,tt+m+1,cmp);
R int s = 0;
for(R int i=1; i<=m; ++i){ //贪心找最少的区间
if(tt[i].r<=s) continue;
R int st = i,to = 0;
while(tt[st].l <= s+1) to = max(to,tt[st++].r);//寻找有区间最远的区间最优
s = to,ans++;
if(s==m) break;
i = st-1;
}
printf("1\n%d",ans);
}

int youngsc = yg();
int main(){;}

啦啦啦

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录
  1. 1. 题目描述
  2. 2. 输入输出格式
    1. 2.1. 输入格式:
    2. 2.2. 输出格式:
    3. 2.3. 输入输出样例
  3. 3. 输入样例#1:
  4. 4. 输出样例#1:
  5. 5. 说明
    1. 5.1. 【样例1 说明】
    2. 5.2. 【样例2 说明】
  6. 6. 【数据范围】
  7. 7. 题目分析
  8. 8. 代码如下
,