WA第一个点。。。应该是最简单的一个点吧。

iMiku @ 2018-09-14 22:21:59

#include<bits/stdc++.h>
using namespace std;
struct he
{
    int x,y,high;
}h[10010];
bool cmp(he a,he b)
{
    return a.high<b.high;
}
int maxheight[110][110],height[110][110];
int r,c,ud[5]={0,1,-1,0,0},lr[5]={0,0,0,-1,1};
int maxn;
int main()
{
    int t=1;
    cin>>r>>c;
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            cin>>height[i][j];
            h[t].x=i;h[t].y=j;h[t++].high=height[i][j];
            maxheight[i][j]=1;
        }
    }
    sort(h+1,h+t,cmp);
    for(int i=1;i<t;i++)
    {
        for(int j=1;j<=4;j++)
        {
            int nx=h[i].x+ud[j];int ny=h[i].y+lr[j];
            bool s=height[nx][ny]>h[i].high;
            if(nx>0&&nx<=r&&ny>0&&ny<=c&&s)
            {
                maxheight[nx][ny]=maxheight[h[i].x][h[i].y]+1;
            }
        }
    }
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            maxn=max(maxn,maxheight[i][j]);
        }
    }
    cout<<maxn;
}

by iMiku @ 2018-09-14 22:22:43

这是老早的题了。。。最近翻出来还是找不到错误

by Sai0511 @ 2018-09-14 22:28:50

@iMiku 是否能讲一下您的思路..我是把整个矩阵遍历一遍然后记忆化搜索做的

by Sai0511 @ 2018-09-14 22:35:30

@iMiku

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int f[1001][1001];
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
int i,j,m,n,a[1001][1001],ans,k,k1;
int dfs(int x,int  y){
    if(f[x][y]!=-1) return f[x][y];
    int i,xa,ya,j,g=0,u;
    bool flag=false;
    for(i=0;i<4;i++){
        xa=x+dir[i][0];
        ya=y+dir[i][1];
        //cout << xa <<' '<< ya << endl;
        if(xa>=1&&xa<=n&&ya>=1&&ya<=n&&a[xa][ya]<a[x][y]){
        //  cout << k<<' '<<k1<<' '<<xa <<' '<< ya<<endl;
            flag=true;
            u=dfs(xa,ya);
            g=max(g,u);
        }
    }
    //cout <<x<<' '<<y<<' ' <<flag << endl;
    //if(x==1&&y==1) cout << flag<<endl;
    if(flag==false){
        f[x][y]=1;
        return 1;
    }  
    f[x][y]=g+1;
    return g+1;

}
int main(){
    cin >> n >> m;
    for(i=1;i<=n;i++)
     for(j=1;j<=m;j++)
      cin >> a[i][j];
      ans=-1;
      memset(f,-1,sizeof(f));
    for(i=1;i<=n;i++)
     for(j=1;j<=m;j++){
      // memset(f,0,sizeof(f));
       //k=i;
       //k1=j;
      // dfs(i,j);
     //  cout <<f[n][m]<<endl;
      // cout << f[n][m] << endl;
       ans=max(ans,dfs(i,j));   
      // cout << ans << endl;
     }  
     //for(i=1;i<=n;i++)
     //for(j=1;j<=n;j++){
      //    cout << "f"<<"["<<i<<']'<<'['<<j<<']'<<f[i][j]<<endl;
      //} 
     cout << ans << endl; 
} 

by iMiku @ 2018-09-14 22:53:25

@Sai_0511 我先将矩阵图存好，再讲矩阵图变成邻接表，从大到小排序，从最高点向下搜索。。类似dp吧