玄学MLE,蒟蒻求助QwQ,用continue会导致MLE?

P1434 [SHOI2002] 滑雪

pipiispig @ 2019-02-10 18:45:10

这是AC了的代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<map>
using namespace std;
inline int read(){
    int f=1,x=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return f*x;
}
int s[101][101];
int dp[101][101];
int n,m;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int dfs(int x,int y){
    if(dp[x][y])return dp[x][y];
    int t=1;
    for(int i=0;i<=3;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>0&&yy>0&&xx<=n&&yy<=m&&s[x][y]>s[xx][yy]){
            t=max(dfs(xx,yy)+1,t);
        }
    }
    dp[x][y]=t;
    return t;
} 
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            s[i][j]=read();
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=dfs(i,j);
            ans=max(dp[i][j],ans);
        }
    }
    cout<<ans<<endl;
} 

这是MLE五个点的

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<map>
using namespace std;
inline int read(){
    int f=1,x=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return f*x;
}
int s[101][101];
int dp[101][101];
int n,m;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int dfs(int x,int y){
    if(dp[x][y])return dp[x][y];
    int t=1;
    for(int i=0;i<=3;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx<=0||yy<=0||xx>n||yy>m||s[xx][yy]>s[x][y])continue;
        t=max(dfs(xx,yy)+1,t);
    }
    dp[x][y]=t;
    return t;
} 
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            s[i][j]=read();
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=dfs(i,j);
            ans=max(dp[i][j],ans);
        }
    }
    cout<<ans<<endl;
} 

2份代码的唯一区别就在于ac了的是if(.&&.&&.&&.&&.){dfe(x,y)}而MLE的是if(..||..||..||..||)continue;dfs(x,y); 我很疑惑为什么第二种会MLE,是因为这个还是因为其他地方,QwQ


by BronyaZaychik @ 2019-02-10 19:11:47

约束条件打错了 用或的应该是

if(xx<=0||yy<=0||xx>n||yy>m||s[xx][yy]>=s[x][y])continue;

by BronyaZaychik @ 2019-02-10 19:12:22

虽然我到现在都没看题干 但是你这个的确忽略了=的情况


by Fatalis_Lights @ 2019-02-10 19:13:17

瞎猜:dfs再s[0][0]的时候凉了。


by without_wings @ 2019-02-11 17:10:21

@sam上帝 inline里不能用while吧。。。我记得这个算复杂语句。


|