FuzeTheHostage @ 2019-05-21 13:41:26

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
using namespace std;
int j,k,map[105][105],maxx=0,xz[5]={0,0,0,-1,1},yz[5]={0,1,-1,0,0};
int dfs(int x,int y){
    int flag=0,ma1=0,ma2=0;
    for(int v=1;v<=4;v++){
        if(x+xz[v]>=1&&x+xz[v]<=j&&y+yz[v]>=1&&y+yz[v]<=k&&map[x][y]>map[x+xz[v]][y+yz[v]]){
            flag=1;
            ma1=dfs(x+xz[v],y+yz[v]);
            if(ma1>ma2){
                ma2=ma1;
            }
        }
    }
    if(!flag){
        return 1;
    }else{
        return ma2+1;
    }
}
int main(){
    cin>>j>>k;
    for(int m=1;m<=j;m++){
        for(int n=1;n<=k;n++){
            cin>>map[m][n];
        }
    }
    for(int m=1;m<=j;m++){
        for(int n=1;n<=k;n++){
            int a=dfs(m,n);
            if(a>maxx){
                maxx=a;
            }
        }
    }
    cout<<maxx;
}

by RainFestival @ 2019-05-21 13:43:40

贴个代码31ms

#include<cstdio>
#include<iostream>
int ans[105][105],a[105][105],n,m,sum,mmax;
int dfs(int x,int y)
{
    if (ans[x][y]) return ans[x][y];
    mmax=0;
    if (a[x+1][y]<a[x][y]) mmax=std::max(mmax,dfs(x+1,y));
    if (a[x][y+1]<a[x][y]) mmax=std::max(mmax,dfs(x,y+1));
    if (a[x-1][y]<a[x][y]) mmax=std::max(mmax,dfs(x-1,y));
    if (a[x][y-1]<a[x][y]) mmax=std::max(mmax,dfs(x,y-1));
    return ans[x][y]=++mmax;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<=n+1;i++)
        for (int j=0;j<=m+1;j++)
            if (i!=0&&i!=n+1&&j!=0&&j!=m+1)
                scanf("%d",&a[i][j]);
            else a[i][j]=10000000;       
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (!ans[i][j]) dfs(i,j);
    sum=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            sum=std::max(ans[i][j],sum);
    printf("%d\n",sum);
    return 0;
}

by FuzeTheHostage @ 2019-05-22 12:52:11

加入了记忆化，达到了34ms

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
using namespace std;
int j,k,map[105][105],map2[105][105],maxx=0,xz[5]={0,0,0,-1,1},yz[5]={0,1,-1,0,0};
int dfs(int x,int y){
    if(map2[x][y]>0){
        return map2[x][y];
    }
    int flag=0,ma1=0,ma2=0;
    for(int v=1;v<=4;v++){
        if(x+xz[v]>=1&&x+xz[v]<=j&&y+yz[v]>=1&&y+yz[v]<=k&&map[x][y]>map[x+xz[v]][y+yz[v]]){
            flag=1;
            ma1=dfs(x+xz[v],y+yz[v]);
            if(ma1>ma2){
                ma2=ma1;
            }
        }
    }
    if(!flag){
        map2[x][y]=1;
        return 1;
    }else{
        map2[x][y]=ma2+1;
        return ma2+1;
    }
}
int main(){
    cin>>j>>k;
    for(int m=1;m<=j;m++){
        for(int n=1;n<=k;n++){
            cin>>map[m][n];
        }
    }
    for(int m=1;m<=j;m++){
        for(int n=1;n<=k;n++){
            int a=dfs(m,n);
            if(a>maxx){
                maxx=a;
            }
        }
    }
    cout<<maxx;
}

by 断罪之翼 @ 2019-05-22 15:35:09

都这么快么。时间复杂度多少啊。

我读完题的第一直觉思路是： 构图--拓扑排序--遍历 O(n)+O(n^2)+O(n)=O(n^2);

by 断罪之翼 @ 2019-05-22 15:35:42

是不是弄复杂了。

by 2007qqc_LiverpoolFC @ 2019-08-24 17:18:34

开O2（氧气）优化