为什么我的记忆化深搜比你的慢?
查看原帖
为什么我的记忆化深搜比你的慢?
998687
chenke7楼主2024/6/6 13:39

如题,我自己敲的记忆化深搜,比答案里面大佬的记忆化搜索要慢几十毫秒,到底哪出了问题?

#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;
}



2024/6/6 13:39
加载中...