Title portal

General idea of the topic

Title Description
In a distant country, there are beautiful lakes on one side and boundless deserts on the other. The administrative division of the country is very special, just forming a rectangle with \ (N \) rows \ (\ times M \) columns, as shown in the above figure. Each grid represents a city, and each city has an altitude.

In order to make the residents drink the clear lake water as much as possible, water conservancy facilities should be built in some cities. There are two kinds of water conservancy facilities: water storage plant and water transmission station. The function of the water storage plant is to pump the water from the lake to the reservoir in the city.
Therefore, only the cities in line \ (1 \) adjacent to the lake can build water storage plants. The function of the water transmission station is to use the height drop through the water transmission pipeline to transport the lake water from high to low. Therefore, the premise for a city to build a water transmission station is that there are adjacent cities with higher altitude and public edge, and water conservancy facilities have been built. Since the city in line \ (N \) is close to the desert and is an arid area of the country, it is required that each city should have water conservancy facilities. So, can this requirement be met? If yes, please calculate the minimum number of water storage plants to be built; If not, find the number of cities in arid areas that cannot have water conservancy facilities.
Input format
Two numbers per line, separated by a space. The first line of input is two positive integers \ (N,M \), representing the size of the rectangle. Next \ (N \) lines, each line \ (M \) positive integers, representing the altitude of each city in turn.
Output format
Two lines. If the requirements can be met, the first line of output is an integer \ (1 \), and the second line is an integer, representing at least several water storage plants; If the requirements cannot be met, the first line of the output is an integer \ (0 \), and the second line is an integer, which means that several cities in arid areas cannot have water conservancy facilities.
Data range: \ (N,M\le 500 \)

Topic analysis

First, judge whether all cities in line \ (N \) can have water conservancy facilities. Obviously, just search it and \ (O(NM) \) is done.
If you can't sweep which cities can't have water conservancy facilities. Now consider the minimum number of impoundments.
First of all, it is not difficult to find that if all cities can build water conservancy facilities, each impoundment can have a continuous interval city in line \ (N \), because if it is not continuous, the middle city will not be able to supply water.
Then we just need to find out that each impoundment can cover the leftmost and rightmost cities. Obviously, we can DP.
Since there may be upward paths, we need to memorize the search complexity \ (O(NM) \).
Finally, just make a segment covering, \ (O(N^2) \) is OK.

#include<cstdio>
#include<cstring>
#include<algorithm>
#define db double
#define gc getchar
#define pc putchar
#define U unsigned
#define ll long long
#define ld long double
#define ull unsigned long long
#define Tp template<typename _T>
#define Me(a,b) memset(a,b,sizeof(a))
Tp _T mabs(_T a){ return a>0?a:-a; }
Tp _T mmax(_T a,_T b){ return a>b?a:b; }
Tp _T mmin(_T a,_T b){ return a<b?a:b; }
Tp void mswap(_T &a,_T &b){ _T tmp=a; a=b; b=tmp; return; }
Tp void print(_T x){ if(x<0) pc('-'),x=-x; if(x>9) print(x/10); pc((x%10)+48); return; }
#define EPS (1e-7)
#define INF (0x7fffffff)
#define LL_INF (0x7fffffffffffffff)
#define maxn 539
#define maxm
#define MOD
#define Type int
#ifndef ONLINE_JUDGE
//#define debug
#endif
using namespace std;
Type read(){
	char c=gc(); Type s=0; int flag=0;
	while((c<'0'||c>'9')&&c!='-') c=gc(); if(c=='-') c=gc(),flag=1;
	while('0'<=c&&c<='9'){ s=(s<<1)+(s<<3)+(c^48); c=gc(); }
	if(flag) return -s; return s;
}
int n,m,h[maxn][maxn];
int f[maxn][maxn],l[maxn][maxn],r[maxn][maxn],las,maxr,ans;
int fx[4]={1,-1,0,0},fy[4]={0,0,1,-1};
void dfs1(int x,int y){
	if(f[x][y]) return; f[x][y]=1;
	int tx,ty,i; for(i=0;i<4;i++){
		tx=x+fx[i]; ty=y+fy[i];
		if(tx<1||tx>n||ty<1||ty>m||h[x][y]<=h[tx][ty]) continue;
		dfs1(tx,ty);
	} return;
}
int check(){
	int i,s=0; for(i=1;i<=m;i++) dfs1(1,i);
	for(i=1;i<=m;i++) if(!f[n][i]) s++;
	if(s){ pc('0'); pc('\n'); print(s); return 1; }
	else return 0;
}
void dfs(int x,int y){
	if(f[x][y]) return; f[x][y]=1;
	int tx,ty,i; for(i=0;i<4;i++){
		tx=x+fx[i]; ty=y+fy[i];
		if(tx<1||tx>n||ty<1||ty>m||h[x][y]<=h[tx][ty]) continue;
		dfs(tx,ty); l[x][y]=mmin(l[x][y],l[tx][ty]); r[x][y]=mmax(r[x][y],r[tx][ty]);
	} return;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(); m=read(); int i,j,k;
	for(i=1;i<=n;i++) for(j=1;j<=m;j++) h[i][j]=read();
	Me(f,0); if(check()) return 0;
	Me(f,0); Me(l,0x3f); Me(r,0); for(i=1;i<=m;i++) l[n][i]=r[n][i]=i;
	for(i=1;i<=m;i++) if(!f[1][i]) dfs(1,i); las=1;
	while(las<=m){
		for(i=1;i<=m;i++) if(l[1][i]<=las) maxr=mmax(maxr,r[1][i]);
		las=maxr+1; ans++;
	} pc('1'),pc('\n'),print(ans);
	return 0;
}