记忆化搜索+贪心

#include<bits/stdc++.h>
using namespace std;
void update(pair<int,int> &x,pair<int,int> y){
	if (x.first==-1)
		x.first=y.first;
	else if (y.first!=-1)
		x.first=min(x.first,y.first);
	if (x.second==-1)
		x.second=y.second;
	else if (y.second!=-1)
		x.second=max(x.second,y.second);
}
pair<int,int> user[600][600];//line n:left,right
bool gone[600][600];
int n,m;
void mems(){
	for (int i=1;i<n;i++){
		for (int j=1;j<=m;j++){
			user[i][j].first=user[i][j].second=-1;
			gone[i][j]=false;
		}
	}
	for (int j=1;j<=m;j++){
		user[n][j].first=user[n][j].second=j;
		gone[n][j]=false;
	}
	return;
}
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool in(int x,int y){
	if (x<1||x>n)
		return false;
	if (y<1||y>m)
		return false;
	return true;
}
int h[600][600];
pair<int,int> dfs(int x,int y){
	//cout<<x<<y<<endl;
	if (gone[x][y])
		return user[x][y];
	gone[x][y]=true;
	for (int i=0;i<4;i++){
		int xi=x+dir[i][0],yi=y+dir[i][1];
		if (in(xi,yi))
			if (h[xi][yi]<h[x][y]){
			update(user[x][y],dfs(xi,yi));
		}
	}
	return user[x][y];
}
int main(){
	cin>>n>>m;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			scanf("%d",&h[i][j]);
	mems();
	for (int i=1;i<=m;i++)
		update(user[1][i],dfs(1,i));
	int cover[m+1][2];
	int cnt=0;
	for (int i=1;i<=m;i++){
		if (user[1][i].first!=-1){
			cnt++;
			cover[cnt][0]=user[1][i].first;
			cover[cnt][1]=user[1][i].second;
			//cout<<" "<<cover[cnt][0]<<":"<<cover[cnt][1]<<endl;
		}
	}
	bool ko[m+1];
	for (int i=1;i<=m;i++){
		ko[i]=false;
	}
	int last=cover[1][0];
	int cmp=1;
	int ret=0;
	while(cmp<=cnt){
		if (last>m)
			break;
		last=max(cover[cmp][0],last);
		while (cmp+1<=cnt&&cover[cmp+1][0]<=last)
			cmp++;
		for (int i=cover[cmp][1];i>=cover[cmp][0];i--){
			if (ko[i])
				break;
			ko[i]=true;
		}
		ret++;
		last=cover[cmp][1]+1;
		//cout<<cover[cmp][0]<<":"<<cover[cmp][1]<<endl;
		cmp++;
	}
	bool xx=true;
	for (int i=1;i<=m;i++){
		if (!ko[i]){
			xx=false;
			break;
		}
	}
	if (xx){
		cout<<"1"<<endl<<ret<<endl;
	}
	else{
		cout<<"0"<<endl;
		ret=0;
		for (int i=1;i<=m;i++)
			if (!ko[i]){
				ret++;
				//cout<<endl<<" "<<i;
			}
		cout<<ret<<endl;
	}
	return 0;
}

T5过不了