P8786 [蓝桥杯 2022 省 B] 李白打酒加强版

我的代码：

#include <iostream>
using namespace std;

int dp[101][101][101];
const int mod = 1e9 + 7;		//题中说了，答案要取模
int main()
{
	int n, m;		//定义遇到店n次，遇花m次
	cin >> n >> m;
	dp[0][0][2] = 1;	//因为题目中说了初始有2斗酒，所以这种情况只有1种方案
	for (int i = 0; i <= n; i++)			//dp[i][j][k]表示，遇到i次店，j次花，还有k斗酒的方案数
	{
		for (int j = 0; j <= m - 1; j++)
		{
			for (int k = 0; k <= m; k++)		//酒数是不可能大于m的，否则最后不可能喝完酒
			{
				if (i==0 && j == 0)	continue;	//当发现遇到0次店，0次花时跳过本次循环（没有意义）
				if (i&&(k % 2 == 0))			//当遇到店的情况时，酒数k一定是偶数，因为翻倍了
				{
					dp[i][j][k] += dp[i - 1][j][k / 2];		//这里直接写dp[i][j][k] = dp[i - 1][j][k / 2]也行，只要确保下一种情况能够将该种情况加上就行。
				}
				if (j)				//遇到花的情况，一定要确保j>0才行，这样遇到花才有意义
				{
					dp[i][j][k] += dp[i][j - 1][k + 1];
				}
				dp[i][j][k] %= mod;			//根据题中要求对结果取余数
			}
		}
	}
	cout << dp[n][m - 1][1];	//因为最后一次遇到的是花，且喝完了酒，所以方案也就是上一次，即遇花m-1次，酒还有1瓶的方案
	return 0;
}

参考：

P8786 [蓝桥杯 2022 省 B] 李白打酒加强版 的题解 - 洛谷专栏

P8786 [蓝桥杯 2022 省 B] 李白打酒加强版 题解 - 洛谷专栏