蓝桥杯2022李白打酒加强版_dp

P2039 - [蓝桥杯2022初赛] 李白打酒加强版 - New Online Judgehttp://oj.ecustacm.cn/problem.php?id=2039

#include <bits/stdc++.h>
using namespace std;
const int N = 128, C = 1e9 + 7;
int dp[N][N][N] = {0}; // dp[i][j][k]存遇到店i次，遇到花j次，剩k斗的可能顺序数量
int n, m;
void solve() {dp[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 > 0 && k % 2 == 0) { // 到店*2得到kdp[i][j][k] = dp[i - 1][j][k / 2];}if (j > 0) { // 遇到花-1得到kdp[i][j][k] = (dp[i][j][k] + dp[i][j - 1][k + 1]) % C;}}}}
}
int main() {ios::sync_with_stdio(false);int T;cin >> T;while (T--) {memset(dp, 0, sizeof(dp));cin >> n >> m;solve();cout << dp[n][m - 1][1] << endl;}return 0;
}