记忆化了为什么还会TLE呢?

P1434 [SHOI2002] 滑雪

抱歉,发错代码了。 ```cpp #include<bits/stdc++.h> using namespace std; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; int n,m; bool vis[102][102]; int a[102][102],f[102][102]; int read() { int x=0;char ch; for(;!isdigit(ch);ch=getchar()); for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x; } int dfs(int x,int y) { int tot=1; if (f[x][y]!=-1) return f[x][y]; for(int i=0;i<4;i++) { if(x+dx[i]>0&&y+dy[i]>0&&x+dx[i]<=n&&y+dy[i]<=m&&!vis[x+dx[i]][y+dy[i]]&&a[x+dx[i]][y+dy[i]]>a[x][y]) { vis[x+dx[i]][y+dy[i]]=true; int q=dfs(x+dx[i],y+dy[i])+1; tot=max(q,tot); vis[x+dx[i]][y+dy[i]]=false; } } return tot; } int main() { memset(f,-1,sizeof(f)); n=read();m=read(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { a[i][j]=read(); } } int ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { memset(vis,false,sizeof(vis)); f[i][j]=dfs(i,j); if(f[i][j]>ans) ans=f[i][j]; } } cout<<ans; return 0; } ```
by 冈崎梦美 @ 2018-01-05 22:18:43


你这个就是暴搜啊 什么值都没记录 f[x][y]是拿来存到某个点的最大值的 在return前加一句f[x][y]=tot; 而且vis数组不用开
by Rorshach @ 2018-01-05 23:39:41


@[Rorshach](/space/show?uid=59303) 谢谢dalao……话说这种sb讨论可以删吗……
by 冈崎梦美 @ 2018-01-06 01:08:56


友情提示,用广搜,深搜记忆的话也有可能超时
by 曼恩薄荷 @ 2018-01-06 13:11:10


|