怎么记忆化搜索？最后一个点T掉了！

ergeda @ 2016-08-26 20:12:27

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int e[110][110];
int p[110][110],ans,m,n,sum1;
void dfs(int i,int j){
    sum1=ans>sum1?ans:sum1;
    if(!p[i+1][j]&&i+1<=m&&e[i][j]>e[i+1][j]){ans++;p[i+1][j]=1;dfs(i+1,j);p[i+1][j]=0;ans--;}
    if(!p[i][j-1]&&j-1>0&&e[i][j]>e[i][j-1]){ans++;p[i][j-1]=1;dfs(i,j-1);p[i][j-1]=0;ans--;}
    if(!p[i-1][j]&&i-1>0&&e[i][j]>e[i-1][j]){ans++;p[i-1][j]=1;dfs(i-1,j);p[i-1][j]=0;ans--;}
    if(!p[i][j+1]&&j+1<=n&&e[i][j]>e[i][j+1]){ans++;p[i][j+1]=1;dfs(i,j+1);p[i][j+1]=0;ans--;}
}
int main(){
    int i,j,k,sum=0;
    scanf("%d%d",&m,&n);
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            scanf("%d",&e[i][j]);
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++){
            memset(p,0,sizeof(p));
            ans=1;
            sum1=0;
            p[i][j]=1;
            dfs(i,j);
            sum=sum1>sum?sum1:sum;
        }
        printf("%d\n",sum);
    return 0;
}

by 1jia1 @ 2016-08-26 21:55:18

记忆化搜索就是每搜一个点就记下答案，然后如果后面刚好遇到这个点就直接加上这个点的答案了，比如：

3 4 2 1 a（1，1）的最优解是3格，那么到了a（1，2），搜到a（1，1）的时候直接加上a（1，1）的最优解就完美了，省了时间。

by winmt @ 2016-11-14 22:16:26

你写的太恶心了。。。懒的看。。。附上我的代码，自己看吧，思路应该差不多。T的一个重要原因可能就是写代码喜欢铺张浪费！

#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<deque>
#include<utility>
#include<map>
#include<set>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<functional>
#include<sstream>
#include<cstring>
#include<bitset>
#include<stack>
using namespace std;
int n,m,ans=-1;
int a[105][105],dp[105][105];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int dfs(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx>=1 && xx<=n && yy>=1 && yy<=m)
        {
            if(a[xx][yy]>=a[x][y])continue;
            if(dp[xx][yy]!=1)dp[x][y]=max(dp[x][y],dp[xx][yy]+1);
            else dp[x][y]=max(dp[x][y],dfs(xx,yy)+1);
        }
    }
    return dp[x][y];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            dp[i][j]=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(dp[i][j]!=1)ans=max(ans,dp[i][j]);
            else ans=max(ans,dfs(i,j));
        }
    }
    printf("%d\n",ans);
    return 0;
}

by ljc20020730 @ 2017-02-25 18:53:02

const dx:array[1..4]of integer=(0,1,0,-1);
      dy:array[1..4]of integer=(-1,0,1,0);
var ans,n,m,i,j,max,min,maxi,maxj,mini,minj:longint;
    f,a:array[1..100,1..100]of longint;
function dfs(x,y:longint):longint;
var i,xx,yy,t,tmp:longint;
begin
 if f[x,y]>0 then exit(f[x,y]);
 t:=1;
 for i:=1 to 4 do begin
  xx:=x+dx[i]; yy:=y+dy[i];
  if (xx>0)and(xx<=n)and(yy>0)and(yy<=m)and(a[xx,yy]>a[x,y]) then begin
  tmp:=dfs(xx,yy)+1;
  if tmp>t then t:=tmp;
  end;
 end;
 f[x,y]:=t;
 exit(t);
end;
begin
 readln(n,m);
 max:=0; min:=maxlongint;
 for i:=1 to n do
  for j:=1 to m do
   read(a[i,j]);
 for i:=1 to n do
  for j:=1 to m do begin
   f[i,j]:=dfs(i,j);
   if f[i,j]>max then max:=f[i,j];
end;
 writeln(max);
end.