[蓝桥杯 2022 省 B] 李白打酒加强版（三维动态规划）

        通过题目描述，我们可以知道这道题目涉及到某种状态时候的方案数，因此我们可以用动态规划来解决问题，并且我们需要注意到酒的状态，因此我们可以用三维数组来存储状态，我们知道N,M最大不会超过100，并且如果酒超过了100斗，即使遇到100朵花也无法喝完，因此只需要定义大小都为100的三维数组即可，并且枚举三种状态，分别是店家，遇到的花以及酒的斗数都进行枚举，根据状态转移方程求得每个状态的方案数量，并且初始化动态数组dp[0][0][2] = 1；因为最后遇到的肯定是花，因此我们只需要输出倒数第二个状态，也就是dp[n][m - 1][1]即可

上代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e2 + 10, mod = 1e9 + 7;

int dp[N][N][N];//dp[i][j][k]表示遇到i个店，j朵花，剩下k斗酒的方案
//当dp[i][j - 1][1]的时候就是答案，因为最后一次肯定是遇到花，并且正好喝完
//需要注意的是，最多遇到的花是100朵此时如果酒多于100斗就相当于答案无效，因为喝不完 
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m;
	dp[0][0][2] = 1;//初始化动态数组 
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= m; j++){
			for(int k = 0; k <= 100; k++){
				//因为上一次从店家出来，因此此时k为偶数，并且i >= 1才可以进行 
				if(k % 2 == 0 && i) dp[i][j][k] = (dp[i - 1][j][k / 2] + dp[i][j][k]) % mod; 
				//上一次遇到了花，因此上一次的状态是k + 1 
				if(j) dp[i][j][k] = (dp[i][j - 1][k + 1] + dp[i][j][k]) % mod;
			} 
		}
	}
	
	cout << dp[n][m - 1][1] << endl;//最后只需要输出dp[n][m][1]的方案即可 
	
	return 0;
}