题目链接：点击打开链接
题目大意：略。
解题思路：通过第一行对应的最后一行的各个区间范围（dfs）来进行（dp）操作。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=510; const int dir[4][2]={-1,0,1,0,0,-1,0,1}; struct node{ int l,r; }seg[maxn][maxn]; int n,m,fail; int g[maxn][maxn], vis[maxn][maxn], dp[maxn]; void init() { fail=0; mem(vis,0); mem(dp,0); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(i!=n) seg[i][j].l=maxn,seg[i][j].r=0; else seg[i][j].l=seg[i][j].r=j; } void dfs(int x,int y) { if(vis[x][y]) return; vis[x][y]=1; for(int i=0;i<4;i++) { int dx=x+dir[i][0], dy=y+dir[i][1]; if(dx<1||dy<1||dx>n||dy>m||g[dx][dy]>=g[x][y]) continue; dfs(dx,dy); seg[x][y].l=min(seg[x][y].l,seg[dx][dy].l); seg[x][y].r=max(seg[x][y].r,seg[dx][dy].r); } } int main() { while(~scanf("%d%d",&n,&m)) { init(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&g[i][j]); for(int j=1;j<=m;j++) dfs(1,j); for(int j=1;j<=m;j++) fail+=!vis[n][j]; if(fail){ printf("0\n%d\n",fail); continue; } for(int j=1;j<=m;j++) { for(int k=seg[1][j].l; k<=seg[1][j].r; k++) { // dp[k]>dp[seg[1][j].l-1] 此题这条件不加也对，看样例，因为如果第1行6这个水站可以假设可以通过8下面对应的， // 那么必须要加这条加以更新，但是此题的特殊性导致6水站受限制于前一个水站的 l（字母） if(!dp[k] || dp[k]>dp[seg[1][j].l-1]) dp[k]=1+dp[seg[1][j].l-1]; } } printf("1\n%d\n",dp[m]); } return 0; }
