洛谷 P1514 【引水入城】

题库：洛谷
题号：1514
题目：引水入城
link ：https://www.luogu.org/problemnew/show/P1514

思路：搜索从第一排开始能覆盖最后一排的区间L ~ R（代码里是x ~ y），但搜索必须满足一个条件才能搜——if(q[1][i - 1] <= q[1][i] && q[1][i + 1] <= q[1][i])，这个条件的原因是如果当前点能覆盖第一排的相邻点，那么选它的相邻点做蓄水厂就没有意义了；而等于号是因为如果它的相邻点覆盖不了它，它就可以选，否则就是无意义的点了。搜索时如果搜到了最后一排，就当前点改为“搜到了”，并存下L和R，L取min，R取max（注意：这里每个点的L和R需要初始化，即L = INF， R = -INF）。搜完以后，判断有没有最后一排的任意一个点没有被改为“搜到了”，如果有就输出“0” + 没有改为“搜到了”的数量。否则就排序 + 贪心区间覆盖——每次贪心取左边界 ≤ l && 右边界 > r的区间（l初始值为1，r初始值为0，然后l每次都重新赋值为r + 1，r反复取 { 左边界 ≤ l && 右边界 > r } 的右边界），最后取最小覆盖的次数（即要安蓄水厂的最小数量）为答案，输出“1” + 最小覆盖的次数。

注：本题建议用深搜，用广搜好像会TLE + MLE

广搜结果：

洛谷 P1514 【引水入城】

搜索结果：

洛谷 P1514 【引水入城】

code：

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 int u[2][4] = {{1, -1, 0, 0}, {0, 0, 1, -1}};
 5 int n, m, q[1001][1001], vis[1001][1001], visn[100001], ans, z;//visn[i]表示最后一排第i列的城市有没有灌到水 
 6 struct node
 7 {
 8     int x, y;
 9 }stu[100001];
10 inline void dfs(int x, int y, int p)//深搜, p表示当前第一排的纵坐标(即要把蓄水厂建到当前位置) 
11 {
12     vis[x][y] = 1;//注意：这个不是最后一排，这个仅仅只是为了不重复搜 
13     if(x == n)//最后一排 
14     {
15         visn[y] = 1;//标记 
16         stu[p].x = min(stu[p].x, y);//min 
17         stu[p].y = max(stu[p].y, y);//max 
18     }
19     for(register int i = 0; i < 4; ++i)
20     {
21         int nx = x + u[0][i];
22         int ny = y + u[1][i];
23         if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && q[x][y] > q[nx][ny]/*这个很重要，不要打等于号哦*/ && !vis[nx][ny])
24         {
25             dfs(nx, ny, p);
26         }
27     }
28     return;
29 }
30 inline int cmp(node a, node b)
31 {
32     return a.x == b.x ? a.y < b.y : a.x < b.x;//三目运算符大法好 
33 }
34 int main()
35 {
36     scanf("%d %d", &n, &m);
37     for(register int i = 1; i <= n; ++i)
38     {
39         for(register int j = 1; j <= m; ++j)
40         {
41             scanf("%d", &q[i][j]);
42         }
43     }
44     for(register int i = 1; i <= m; ++i)//这是纵坐标，所以是m 
45     {
46         stu[i].x = INF;//初始化 
47         stu[i].y = -INF;
48     }
49     for(register int i = 1; i <= m; ++i)//这是纵坐标，所以是m 
50     {
51         if(q[1][i - 1] <= q[1][i] && q[1][i + 1] <= q[1][i])
52         {
53             memset(vis, 0, sizeof(vis));//初始化 
54             dfs(1, i, i);
55         }
56     }
57     for(register int i = 1; i <= m; ++i)
58     {
59         if(!visn[i])//没有灌到水的 
60         {
61             ++ans;
62         }
63     }
64     if(ans)//有没有灌到水的 
65     {
66         printf("0
%d", ans);
67         return 0;
68     }
69     for(register int i = 1; i <= m; ++i)//重新赋值一遍
70     {
71         if(stu[i].x != INF && stu[i].y != -INF)//前提是这个点被安了蓄水厂 
72         {
73             stu[++z].x = stu[i].x;
74             stu[z].y = stu[i].y;
75         }
76     }
77     sort(stu + 1, stu + z + 1, cmp);//按左端点排序 
78     int l = 1;
79     int j = 1;
80     int r = 0;
81     for(; l <= m/*超了右端点就停止*/; l = r + 1/*更新左端点*/, r = 0/*每次赋值为0*/, ++ans/*最小覆盖的次数(蓄水厂的最小数量)*/)//for循环大法好 
82     {
83         while(stu[j].x <= l)
84         {
85             r = max(r, stu[j].y);//取max 
86             ++j;//别忘了继续循环下一个点 
87         }
88     }
89     printf("1
%d", ans);
90     return 0;
91 }

洛谷 P1514 【引水入城】

相关推荐