由于楼上有一位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卡过去的……