感觉这波记忆化搜索本来能吹一年,结果考场上没想到怎么优化空间交的dfs混分
题目描述
话说大诗人李白,一生好饮。
幸好他从不开车。
一天,他提着酒壶,从家里出来,酒壶中有酒 2 斗。
他边走边唱:
无事街上走,提壶去打酒。
逢店加一倍,遇花喝一斗。
这一路上,他一共遇到店 N 次,遇到花 M 次。
已知最后一次遇到的是花,他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序,有多少种不同的可能?
注意:壶里没酒 (0 斗) 时遇店是合法的,加倍后还是没酒;但是没酒时遇花是不合法的。
样例
输入
5 10
输出
14
(三维)记忆化搜索
建出三维数组,下表依次表示店的数量,花的数量和酒的数量,memset为-1标记是否被访问过
如访问过则直接返回这个值,如果没访问过则求解并记录
考场上没想到酒的数量一旦大于101(超出花的最大数量)就无法实现题目要求,所以不知道该开多大的数组,其实开105就够,因为对于大于105的部分一定无法满足(恰好喝完)所以直接返回0,即这个条件下不能满足题目的要求,算0种(不算)满足的情况
C++ 代码
//不确定对不对,现在网上oj数据能a
#include<iostream>
#include<cstring>
using namespace std;
#define mod 1000000007
int ans[105][105][105];//分别表示:店、花、酒
int solve(int n,int m,int wine){
int as=0;
if(ans[n][m][wine]!=-1)return ans[n][m][wine];//如果被访问过直接返回这个值,减少重复运算
if(n==0&&m==1&&wine==1)return 1;//恰好花和酒都为1时,可以满足题目要求
if(wine>105||wine<0)return 0;//如果酒提前喝完或超出花的最大数(能喝的最大数)则直接返回0
if(n>0&&m>= 0)as+=solve(n-1,m,wine*2);//递归
if(n>=0&&m>0)as+=solve(n,m-1,wine-1);//递归
return ans[n][m][wine]=as%mod;//返回
}
int main(){
// int t; //原题有多组输入但这里没有,之前交了两发多组输入都寄了
// cin>>t;
// while(t--){
int n,m;
cin>>n>>m;
memset(ans,-1,sizeof(ans));//初始化,用-1标记
cout<<solve(n,m,2);
// }
return 0;
}
#### C++ 代码
应该把判断wine是否大于101放在判断是否访问之前以防止数组越界