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

题目链接：

思路：

①定义dp数组，f[i][j][k]，表示经过 i 店， 遇到 j 花， 还有 k 酒。如果酒的数量超过了花的数量，那么一定喝不完。因此，k 不能超过 M。

②从店推过来，f[i][j][k] += f[i-1][j][k/2]，要保证 i-1 和 k/2 符合，所以 i >= 1 并且 k 能被2整除。

③从花推过来，f[i][j][k] += f[i][j-1][k+1]，要保证 j-1 和 k+1 符合，所有 j >= 1并且 k >= -1（省略，k一定大于0）。

④题目规定最后一定遇到花，并且刚好喝完酒，因此，输出 f[n][m-1][1]。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 110, MOD = 1e9+7;int n, m;
//dp数组
//表示经过i家店 j躲花 还剩下 k 酒
int f[N][N][N];signed main(){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 <= m; k++){//店if(i && (k%2==0)){f[i][j][k] += f[i-1][j][k/2];f[i][j][k] %= MOD;}if(j){f[i][j][k] += f[i][j-1][k+1];f[i][j][k] %= MOD;}}}}cout << f[n][m-1][1] << endl;return 0;
}