李白打酒加强版
题目大意
一开始酒显里有 \(2\) 斗酒，每遇到一次店就会把酒显里的酒数量(单位: 斗)乘 \(2\)，每遇到一次花就把酒显里的酒喝掉 \(1\) 斗。
这一路上一共遇到店 \(n\) 次，遇到花 \(m\) 次，且最后一次遇到的是花，酒显里没有一斗酒了。
计算这一路上遇到店和花的顺序总共有多少种可能(答案模 \(1e9 + 7\))。
允许 \(0\) 斗酒时遇到店，不允许 \(0\) 斗酒时遇到花。
思路
这题我一眼就看出是一个动态规划题 (因为看了标签)。
由于最后一次固定为遇到花，所以可以先把 \(m\) 减去 \(1\)。
- 状态：
dp[i][j][k]表示来到第 \(i\) 处地点，遇到店 \(j\) 次，酒显里还有 \(k\) 斗酒的方案数。 - 转移方程：
- 遇到店：
dp[i - 1][j - 1][k / 2]转移到dp[i][j][k](需保证 \(j \geqslant 1\) 并且 \(k\) 为偶数) - 遇到花：
dp[i - 1][j][k + 1]转移到dp[i][j][k]。
- 遇到店：
- 初始状态：
dp[0][0][2] = 1 - 目标状态：
dp[n + m][n][1]
很显然，如果直接连续一百次遇到店(酒显里还有酒时)，酒显里的酒的斗数就会变得很大。
但是，要想喝最多 \(100\) 斗就能喝完，当酒的斗数在任何时候超过 \(100\) 的情况是不用讨论的，因为喝不完了。
一定要记得取模。
代码
#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
int n, m;
int dp[210][110][110]; // 注意数组大小
int main(){
cin >> n >> m;
m--, dp[0][0][2] = 1; // 初始状态
for (int i = 1; i <= n + m; i++){ // 一共 n + m 处地点
for (int j = 0; j <= min(n, i); j++){ // 最多只能遇店 n 次，但是也不能超过 i 次
for (int k = 0; k <= 100; k++){ // 100 以上不用考虑
dp[i][j][k] = dp[i - 1][j][k + 1]; // 遇到花
if (k % 2 == 0 && j){ // 满足要求，可以遇到店
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][k / 2]) % mod; // 状态转移方程，记得取模
}
}
}
}
cout << dp[n + m][n][1]; // 输出目标状态
return 0;
}