洛谷 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

广搜结果：

搜索结果：

code：

 #include <bits/stdc++.h>

 #define INF 0x3f3f3f3f

 using namespace std;

 int u[][] = {{, -, , }, {, , , -}};

 int n, m, q[][], vis[][], visn[], ans, z;//visn[i]表示最后一排第i列的城市有没有灌到水

 struct node

 {

     int x, y;

 }stu[];

 inline void dfs(int x, int y, int p)//深搜, p表示当前第一排的纵坐标(即要把蓄水厂建到当前位置)

 {

     vis[x][y] = ;//注意：这个不是最后一排，这个仅仅只是为了不重复搜

     if(x == n)//最后一排

     {

         visn[y] = ;//标记

         stu[p].x = min(stu[p].x, y);//min

         stu[p].y = max(stu[p].y, y);//max

     }

     for(register int i = ; i < ; ++i)

     {

         int nx = x + u[][i];

         int ny = y + u[][i];

         if(nx >=  && nx <= n && ny >=  && ny <= m && q[x][y] > q[nx][ny]/*这个很重要，不要打等于号哦*/ && !vis[nx][ny])

         {

             dfs(nx, ny, p);

         }

     }

     return;

 }

 inline int cmp(node a, node b)

 {

     return a.x == b.x ? a.y < b.y : a.x < b.x;//三目运算符大法好

 }

 int main()

 {

     scanf("%d %d", &n, &m);

     for(register int i = ; i <= n; ++i)

     {

         for(register int j = ; j <= m; ++j)

         {

             scanf("%d", &q[i][j]);

         }

     }

     for(register int i = ; i <= m; ++i)//这是纵坐标，所以是m

     {

         stu[i].x = INF;//初始化

         stu[i].y = -INF;

     }

     for(register int i = ; i <= m; ++i)//这是纵坐标，所以是m

     {

         if(q[][i - ] <= q[][i] && q[][i + ] <= q[][i])

         {

             memset(vis, , sizeof(vis));//初始化

             dfs(, i, i);

         }

     }

     for(register int i = ; i <= m; ++i)

     {

         if(!visn[i])//没有灌到水的

         {

             ++ans;

         }

     }

     if(ans)//有没有灌到水的

     {

         printf("0\n%d", ans);

         return ;

     }

     for(register int i = ; i <= m; ++i)//重新赋值一遍

     {

         if(stu[i].x != INF && stu[i].y != -INF)//前提是这个点被安了蓄水厂

         {

             stu[++z].x = stu[i].x;

             stu[z].y = stu[i].y;

         }

     }

     sort(stu + , stu + z + , cmp);//按左端点排序

     int l = ;

     int j = ;

     int r = ;

     for(; l <= m/*超了右端点就停止*/; l = r + /*更新左端点*/, r = /*每次赋值为0*/, ++ans/*最小覆盖的次数(蓄水厂的最小数量)*/)//for循环大法好

     {

         while(stu[j].x <= l)

         {

             r = max(r, stu[j].y);//取max

             ++j;//别忘了继续循环下一个点

         }

     }

     printf("1\n%d", ans);

     return ;

 }

巴特西

洛谷 P1514 【引水入城】

最新文章

热门文章