本文共 1599 字，大约阅读时间需要 5 分钟。

题目链接：

题目大意：略。

解题思路：通过第一行对应的最后一行的各个区间范围（dfs）来进行（dp）操作。

AC 代码

#include
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a);#define INF 0x3f3f3f3fusing 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;}
    
   

转载地址：https://lux-sun.blog.csdn.net/article/details/81148040 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！