返回题解分享
讨论 / 题解分享/ 帖子详情

李白打酒加强版(编程题) - 题解

#### 记忆化搜索

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
const int mod = 1e9+7;
int dp[maxn][maxn][maxn];
int dfs(int x,int y,int z){ //酒量,遇见店的次数,遇到花的次数 
	if(x<0 || y<0 || z <0) return 0;
	if(x>z) return 0;
	if(z==1)return y==0 && x==1; //最后一次 
	if(dp[x][y][z] != -1)return dp[x][y][z];
	dp[x][y][z] = (dfs(x*2,y-1,z)+dfs(x-1,y,z-1))%mod;
	return dp[x][y][z];
}
int main(){
	memset(dp,-1,sizeof dp);//初始化-1 
	int n,m;
	cin >> n >> m;
	cout << dfs(2,n,m) << endl;
	return 0;
}
0 回复 0 转发 0 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!