qd_zhanghuali @ 2019-05-24 23:06:51

#include<iostream>
using namespace std;
int a[101][101],ma=1;
bool book[101][101];
int fx[4][2]={0,1,1,0,0,-1,-1,0},m,n;
void dfs(int x,int y,int c);
int main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++){
    for(int u=1;u<=n;u++)cin>>a[i][u];
}
for(int i=1;i<=m;i++){
    for(int u=1;u<=n;u++){
        if(ma==m*n)break;
        if(book[i][u]==1)continue;
        dfs(i,u,1);
    }
}
cout<<ma;
}
void dfs(int x,int y,int c){
if(c>ma)ma=c;
for(int i=0;i<4;i++){
    int f=x+fx[i][0],g=y+fx[i][1];
    if(f>0&&g>0&&f<=m&&g<=n&&a[f][g]>a[x][y])dfs(f,g,c+1);
}
}

by MikukuOvO @ 2019-05-24 23:32:32

emm

by MikukuOvO @ 2019-05-24 23:32:57

您直接进行搜索复杂度没得保证啊

by MikukuOvO @ 2019-05-24 23:34:49

而且您的book并没有用上哇，可能是想记搜？

by MikukuOvO @ 2019-05-24 23:36:28

但是吸氧也没过，应该是RE了吧

by MikukuOvO @ 2019-05-24 23:42:48

好吧，应该是爆搜太慢了

by MikukuOvO @ 2019-05-24 23:43:07

int a[101][101],ma=1,map[101][101];
int fx[4][2]= {0,1,1,0,0,-1,-1,0},m,n;

void dfs(int x,int y,int c);
int main()
{
    cin>>m>>n;
    for(int i=1; i<=m; i++)
    {
        for(int u=1; u<=n; u++) scanf("%d",&a[i][u]);
    }
    for(int i=1; i<=m; i++)
    {
        for(int u=1; u<=n; u++)
        {
            dfs(i,u,1);
        }
    }
    cout<<ma;
}
void dfs(int x,int y,int c)
{
    if(x<=0||x>m||y<=0||y>n) return;
    if(map[x][y]>=c) return;
    else map[x][y]=c;
    if(c>ma) ma=c;
    for(int i=0; i<4; i++)
    {
        int f=x+fx[i][0],g=y+fx[i][1];
        if(a[f][g]>a[x][y]) dfs(f,g,c+1);
    }
}

by MikukuOvO @ 2019-05-24 23:43:19

加一个记搜就好了

by qd_zhanghuali @ 2019-05-25 12:57:34

@⚡DAG⚡只有测试点二TIE超时了，90分

by AlexGu @ 2019-06-22 15:09:19

include<iostream>

include<cstdio>

using namespace std; int n,m,a[101][101],bs=1,f[101][101]; int dx[5]={0,1,0,-1,0}; int dy[5]={0,0,1,0,-1}; int dfs(int x, int y) { if(f[x][y]!=0) return f[x][y]; int maxt=1,t; for(int i=1;i<=4;i++) { if(x+dx[i]>0&&x+dx[i]<=n&&y+dy[i]>0&&y+dy[i]<=m&&a[x+dx[i]][y+dy[i]]<a[x][y]) { t=dfs(x+dx[i],y+dy[i])+1; if(t>maxt) maxt=t; } } f[x][y]=maxt; return maxt; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { f[i][j]=dfs(i,j); if(f[i][j]>bs) bs=f[i][j]; } } cout<<bs; return 0; }