记忆化+区间覆盖

通过记忆化得到每个点可以覆盖的区间的数目,然后按照区间覆盖进行贪心即可。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define l first
#define r second
const int N=510;
int n,m;
int h[N][N];
PII f[N][N];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
void dfs(int x,int y)
{
	PII& p=f[x][y];
	if(p.l!=-1) return ; //已经被计算过了
	p.l=N;//初始化可以覆盖的左边的最小值
	p.r=0;
	if(x==n) p={y,y}; //当前点的行列 
	for(int i=0;i<4;i++)
	{
		int a=x+dx[i],b=y+dy[i];
		if(a>=1&&a<=n&&b>=1&&b<=m&&h[a][b]<h[x][y])
		{
			dfs(a,b); //计算周围的点
			p.l=min(p.l,f[a][b].l); //更新左边值 
			p.r=max(p.r,f[a][b].r); //更新右边界 
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>h[i][j];
		}
	}
	memset(f,-1,sizeof f);
	for(int i=1;i<=m;i++)
	{
		dfs(1,i);//计算第一行的每个元素可以覆盖的区间 
	}
	int cnt=0;
	for(int i=1;i<=m;i++)
	{
		if(f[n][i].l==-1)
		{
			cnt++;
		}
	}
	if(cnt)
	{
		cout<<0<<endl<<cnt<<endl;
	}
	else
	{
		vector<PII> segs;
		for(int i=1;i<=m;i++)
		{
			segs.push_back({f[1][i]});
		}
		sort(segs.begin(),segs.end());//按照区间左端点排序 
		int res=0;
		for(int i=0,start=1;i<m;)
		{
			int maxr=0;
			while(i<m&&segs[i].l<=start) //还在当前区间内 
			//选择当前这个区间可以走到的最远的地方 
			{
				maxr=max(maxr,segs[i].r);
				i++;
			}
			res++; //选择当前这个区间 
			if(maxr>=m) break; //已经覆盖完成 
			start=maxr+1; //从下一个点开始覆盖 
		}
		cout<<1<<endl<<res<<endl;
	}
	return 0;
}