``` #include<bits/stdc++.h> using namespace std; int f[205][101][105]; int m,n; int main(){ //ios::sync_with_stdio(false),cout.tie(0),cin.tie(0); cin>>n>>m; //初生两斗酒=1 f[0][0][2]=1; //i个位置，看了j次花，有k斗酒的方案或者经过酒店 for(int i=0;i<=n+m;i++) for(int j=0;j<m;j++)//注意是m-1，因为最后一次必须是花，且如果算上m+1这样还会多算 for(int k=0;k<=m;k++) ``` ``` if(f[i][j][k]!=0) { if(k>0)f[i+1][j+1][k-1]=(f[i+1][j+1][k-1]+f[i][j][k])%1000000007; if(k<=50)f[i+1][j][k*2]=(f[i+1][j][k*2]+f[i][j][k])%1000000007; } ``` ``` //注意题目中M<=100所以k不能大于50 cout<<f[n+m][m][0]; ``` ``` return 0; ``` } ``` ```

题解 显然我们马上可以思考到dp 现在定义状态: - 第 $i$ 次经过酒店, 第 $j$ 次遇到花, 剩下酒为 $k$ 的方案数为 $f[i][j][k]$ 有如下状态转移方程: - 如果 k 是偶数: $f[i][j][k] = f[i - 1][j][k / 2] + f[i][j - 1][k + 1]$ - 如果 k 不是偶数, (说明不能是经过店后的状态): $f[i][j][k] = f[i][j - 1][k + 1]$ 注意题目要求: 已知最后一次遇到的是花，他正好把酒喝光了 && 没酒时遇花是不合法的 所以我们最终的结果是: $f[n][m - 1][1]$ (第 n 次经过店, 第 m - 1 次 经过花, 并且水壶中有酒 1 斗), 这样可以规避 $f[n][m][0] = f[i - 1][j][0] + ...$ 的情况(而外计算了从店来的方案数, 不符合最后一次遇到的是花) 至于 k 为什么 最大是 100 ? - 因为考虑到它需要花费到为 0, 不然你可能会被开2 << 100的范围给 k, 但是它不合法, 所以也不需要. 再至于为什么 i, j, 在 $f$ 中也是 从 0 开始, 并且特判 i, j, 为什么不再 init 的时候赋值 f[0][1][k], f[1][0][k], 然后从 i = 1, j = 1 开始? - 因为这样会丢失 f[0][j][k] 和 f[i][0][k] 的数据! 代码 ```C++ #include <cstdio> #include <iostream> #include <algorithm> #include <utility> #include <queue> #include <map> #include <set> #include <vector> #include <tuple> #include <functional> #include <unordered_set> #include <unordered_map> #include <list> #include <cmath> using namespace std; using ll = long long; const int inf = 1e9; const int mod = 1e9 + 7; int main() { int n, m; cin >> n >> m; vector<vector<vector<ll>>> f(n + 1, vector<vector<ll>>(m + 1, vector<ll>(100, 0))); f[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) { if (k % 2 == 0 && i) f[i][j][k] += f[i - 1][j][k >> 1]; if (j) f[i][j][k] += f[i][j - 1][k + 1]; f[i][j][k] %= mod; } } } // 已知最后一次遇到的是花 // 相当于: 第 n 次经过店, 第 m - 1 次 经过花, 并且水壶中有酒 1 斗 cout << f[n][m - 1][1] << '\n'; return 0; } ```

```c++ #include <bits/stdc++.h> #define int long long using namespace std; const int N = 110; int n, m; int f[N][N][N]; int mod = 1e9 + 7; signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; f[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 ++ ){ if(i == 0 && j == 0) continue; if(i > 0 && k % 2 == 0) { f[i][j][k] = (f[i][j][k] + f[i - 1][j][k / 2]) % mod; } if(j > 0) { f[i][j][k] = (f[i][j][k] + f[i][j - 1][k + 1]) % mod; } } f[n][m][0] = f[n][m - 1][1]; cout << f[n][m - 1][1]; // 最后一步只有一种可能 } ```

记忆化搜索 ``` #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; } ```

mod = 1e9+7 n,m = map(int,input().split()) dp = [[[0 for i in range(105)] for i in range(105)] for j in range(105) ] dp[0][0][2] =1 for i in range(n+1): for j in range(m+1): for k in range(100): if k%2==0 and i : dp[i][j][k] = (dp[i][j][k] +dp[i-1][j][int(k/2)])%mod if j: dp[i][j][k] = (dp[i][j][k]+dp[i][j-1][k+1])%mod print(int(dp[n][m-1][1]))