搜索。
-
首先先用 \(dfs\) 判断一下对于每一个点来说对应的可以覆盖的 \(L,R\) . 假设题目一定存在一个解，所以一定会有该点覆盖的区间连续。设该区间为 \(L,R\) ， 若不是每一个点均会被覆盖 ，那么题目不会存在任何一个解。
-
判断是否有解：跑一遍 \(dfs\) ，记录每一个点被 \(dfs\) 覆盖的情况，有多少个点未被覆盖那么就会有多少个点一定无解，此时如果无解点数 \(>\) 1 那么就必有题目无解的情况存在。
-
寻找最优解。贪心地做一遍线段覆盖即可。
但是这样时间复杂度瓶颈在于搜索部分，设对于任意点均有一种方案搜索到全局，那么此时的复杂度为 \(\Theta(n^2)\) 的，那么因为全局共有 \(n\) 个点，所以复杂度瓶颈为 \(\Theta(n^3)\) 。 然后可以考虑一下记忆化搜索。对每一个点取两个记忆：
\[[L,R] \]然后可以考虑维护记忆化，转移的话就是 \(L_i=\min\{L_{j\in i}\} ， R_i=\min\{R_{j \in i}\}\) 其中属于表示可以取到。
然后这样的话复杂度可以压缩到 \(O(n^2)\) ，相当小，这样就能够跑掉这道题了。
代码的话关注一下搜索的转移过程、线段覆盖的经过就行了。
#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define add push_back
const int N=4e3+5;
int h[N][N];
bool vis[N][N];
bool cf[N];
int left[N][N],right[N][N];
struct line{int l,r;}d[N];
const int dirx[]{0,0,1,0,-1};
const int diry[]{0,1,0,-1,0};
bool cmp(line ax,line ay){
if(ax.l!=ay.l) return ax.l<ay.l;
return ax.r > ay.r;
}
int n,m;
bool judge(int x,int y,int px,int py){
if(x<1 || x>n || y<1 || y>m) return false;
if(h[px][py] <= h[x][y])return false;
return true;
}
void dfs(int x,int y){
// printf("dfs x=%d,y=%d\n",x,y);
vis[x][y]=true;
for(register int i=1;i<=4;++i){
int nx=x+dirx[i],ny=y+diry[i];
if(!judge(nx,ny,x,y)) continue;
if(!vis[nx][ny]) dfs(nx,ny);
left[x][y]= std::min(left[x][y],left[nx][ny]);
right[x][y]= std::max(right[x][y],right[nx][ny]);
}
// printf("left = %d , right=%d;\n",left[x][y],right[x][y]);
}
void work(int u){
dfs(1,u);
int L=left[1][u],R=right[1][u];
d[u]={L,R};
// printf("L=%d,R=%d,u=%d\n",L,R,u);
return;
}
void Init(void){
memset(left,127,sizeof left);
for(register int i=1;i<=m;++i)
left[n][i]=i,right[n][i]=i;
}
int main(){
scanf("%d%d",&n,&m);Init();
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
scanf("%d",&h[i][j]);
for(register int i=1;i<=m;++i)
work(i);
int cnt=0;
for(register int i=1;i<=m;++i){
if(!vis[n][i])++cnt;
}
if(cnt){
printf("0\n%d\n",cnt);
return 0;
}
std::sort(d+1,d+n+1,cmp);
int index=1,num=1,ans=0;
while(num<=m){
int tmp=0;
while(d[index].l<=num)
tmp=std::max(tmp,d[index].r),
++index;
num=tmp+1;
++ans;
}
puts("1");
std::cout<<ans<<std::endl;
return 0;
}