记忆化搜索解法

071maozihan 2022-08-02 13:32:22 2022-08-03 7:58:37 24 返回题目

由于楼上有一位dalao提到了动态规划,也提出了dp的解法

那既然提到了动规,怎能没有记忆化搜索

于是蒟蒻就专门写了一篇记搜作为题解

#include<bits/stdc++.h>
using namespace std;
const long long maxn=5e3+10,P = 1e9+7;
int n,m;
int mem[maxn][maxn][2];
int DFS(int x,int y,bool lock){
	//DFS函数表示第一层到第x层,锁上y个箱子,第x+1层箱子是否锁上时,有几种情况 
	if(y<0)return 0; //不可能锁上负数个箱子 
	if(x == 0){ //第零层代表搜索出口 
		if(y == 0)return 1;  
		return 0;
	}
	if(mem[x][y][(int)lock] != -1)return mem[x][y][(int)lock];//记忆化 
	long long tmp = 0;//OI比赛十年功,不开longlong见祖宗 
	if(lock){ //判断上一个箱子是否锁上 
		tmp+=DFS(x-1,y,0);
		tmp%=P; 
		tmp+=DFS(x-1,y-1,1);
		tmp%=P;
	}
	else{
		tmp+=DFS(x-1,y,0);
		tmp%=P;
		tmp+=DFS(x-1,y,1);
		tmp%=P;
	}
	return mem[x][y][(int)lock] = tmp;//记录状态 
}
signed main()
{
	scanf("%d %d",&n,&m); //输入 
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			for(int k=0;k<=1;k++){
				mem[i][j][k] = -1; //对mem数组作初始化
				//本蒟蒻不会memset…… 
			}
		}
	}
	cout<<DFS(n,m,1)<<endl;//直接输出,搜索交给电脑 
	return 0;
}

接下来,就愉快的AC吧~

哦哦,顺带提一句,本算法时间复杂度为O(2*mn),常数项省略后大约为O(mn)

但,n,m最大毕竟有5000,因此常数最好不要忽略……

所以最后也是900多ms卡过去的……

{{ vote && vote.total.up }}