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吧。。。我记得这个算复杂语句。