如题,我自己敲的记忆化深搜,比答案里面大佬的记忆化搜索要慢几十毫秒,到底哪出了问题?
#include<bits/stdc++.h>
using namespace std;
int a[25][25];
int dp[25][25][25][25];
int n,x,y,z;
int ans;
int dx[]={1,1,0,0};//第一个点的变化
int dy[]={0,0,1,1};
int dx2[]={1,0,1,0};//第二个点的变化
int dy2[]={0,1,0,1};
void dfs(int x,int y,int h,int l,int sum1)
{
//如果之前已经搜索过这个地方了,且这个地方之前搜索的答案更优,直接砍掉
if (dp[x][y][h][l]>sum1) return;
else dp[x][y][h][l]=sum1;
//如果走到了终点
if (x==n and y==n and h==n and l==n)
{
ans=max(ans,sum1);
return;
}
//两个点的四种前进方向,下下,下右,右下,右右
for(int i=0;i<4;i++){
int xx=x+dx[i];
int yy=y+dy[i];
int hh=h+dx2[i];
int ll=l+dy2[i];
//防止越界
if (xx>=1 and xx<=n and yy>=1 and yy<=n and hh>=1 and hh<=n and ll>=1 and ll<=n)
{
//如果两个点在一起
if (xx==hh and yy==ll)
{
dfs(xx,yy,hh,ll,sum1+a[xx][yy]);
}
else dfs(xx,yy,hh,ll,sum1+a[xx][yy]+a[hh][ll]);
}
}
}
int main()
{
cin>>n;
while(1){
cin>>x>>y>>z;
if (x==0) break;
a[x][y]=z;
}
memset(dp,-1,sizeof dp);
dfs(1,1,1,1,a[1][1]);
cout<<ans;
return 0;
}