P1514 引水入城（搜索+线段完全覆盖）

  1 //先做搜索，再做线段覆盖
  2 //前提是从一个点出发的水能到达的旱地一定是连续的
  3 //洛谷题解有证明
  4 #include<iostream>
  5 #include<cstring>
  6 #include<algorithm>
  7 #include<limits.h>
  8 using namespace std;
  9 int n,m;
 10 int mp[600][600];
 11 int vis[600][600];//搜索用的
 12 int visn[600];//存储所有的旱地能否到达
 13 //存储线段
 14 struct node
 15 {
 16     int x,y;
 17 }xd[600];
 18 //方向
 19 int u[]= {-1,0,1,0};
 20 int v[]= {0,1,0,-1};
 21 
 22 
 23 
 24 void dfs(int x,int y,int p)//搜索，x，y表示当前的位置，p表示蓄水（出发）的点
 25 {
 26     vis[x][y]=1;
 27     if(x==n)//前提是连续
 28     {
 29         visn[y]=1;
 30         xd[p].x=min(xd[p].x,y);
 31         xd[p].y=max(xd[p].y,y);
 32     }
 33     for(int i=0; i<4; i++)
 34     {
 35         int xx=x+u[i];
 36         int yy=y+v[i];
 37         if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&mp[xx][yy]<mp[x][y]&&!vis[xx][yy])
 38         {
 39             dfs(xx,yy,p);
 40         }
 41     }
 42 }
 43 
 44 
 45 
 46 bool cmp(node a,node b)
 47 {
 48     if(a.x==b.x)
 49         return a.y<b.y;
 50     return a.x<b.x;
 51 }
 52 int main(void)
 53 {
 54     memset(visn,0,sizeof(visn));
 55     cin>>n>>m;
 56     for(int i=1; i<=n; i++)
 57     {
 58         for(int j=1; j<=m; j++)
 59         {
 60             cin>>mp[i][j];
 61         }
 62     }
 63     for(int i=1; i<=m; i++)
 64     {
 65         xd[i].x=INT_MAX;
 66         xd[i].y=INT_MIN;
 67     }//初始化
 68     for(int i=1; i<=m; i++)
 69     {
 70         if(mp[1][i]>=mp[1][i-1]&&mp[1][i]>=mp[1][i+1])//如果一个出发点不比左右都高那就没必要建蓄水池，因为建在比他高的地方一定更优
 71                                                     //其实对于这个题也没有什么干系，这个也算是一个剪枝吧
 72         {
 73             memset(vis,0,sizeof(vis));
 74             dfs(1,i,i);
 75         }
 76     }
 77     //以上是区间搜索
 78     //下面是线段覆盖
 79     int ans=0;
 80     for(int i=1; i<=m; i++)
 81     {
 82         if(!visn[i])
 83         {
 84             ans++;
 85         }
 86     }//判断是否有到不了的旱地
 87     if(ans)
 88     {
 89         cout<<"0"<<endl<<ans;
 90     }
 91     else
 92     {
 93         int z=1;
 94         for(int i=1; i<=m; i++) //把建了蓄水厂的点挑出来
 95         {
 96             if(xd[i].x!=INT_MAX&&xd[i].y!=INT_MIN)
 97             {
 98                 xd[z++]=xd[i];
 99             }
100         }
101         sort(xd+1,xd+z,cmp);
102         int l=1,r=0;
103         int j=1;
104         while(l<=m)//下面就是一个区间完全覆盖，看（差不多算抄的了）了好久
105         {
106             while(xd[j].x<=l)
107             {
108                 r=max(r,xd[j].y);
109                 j++;
110             }
111             ans++;
112             l=r+1;
113             r=0;
114         }
115         cout<<"1"<<endl<<ans;
116     }
117     return 0;
118 }
但是这样写好像会爆栈，开O2才能过，至于dp（好像还能记忆化搜索），立个flag，一定补