算法竞赛2022年第十三届蓝桥杯C++ B组_李白打酒加强版
// https://www.acwing.com/problem/content/4412/
// 代码已经通过测试
#include<cstdio>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
const int maxn = 105;
long long dp[maxn][maxn][maxn] ;
int main() {
int n, m;
n=3;m=10;
cin >> n >> m;
// 初始化 dp
dp[0][0][2] = 1;
for (int i = 0; i <= n ; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 1; k <= m; k++) {
// 遇到了花后抵达第 (i,j) 步
if(j>0)
dp[i][j][k] = (dp[i][j][k] + dp[i ][j-1][k + 1]) % MOD;
// 遇到了酒馆后抵达第 (i,j) 步
// 当 k % 2 == 0 时才有可能是从酒馆走来的，因为经过酒馆后酒就加倍了
if (i>0 && k%2 == 0) {
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k / 2]) % MOD;
}
}
}
}
cout << dp[n ][ m -1][1] << endl;
return 0;
}
/*
#include<cstdio>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
long long ans=0;
int n, m;
vector<char> temp;
void backTrack( int nn, int mm, int wine) {
if (nn > n || mm > m) return;
if (temp.size() == n + m) {
if (wine == 0 && temp.back() == '0') { // 最后到达必须是花，符合条件
ans+=1;
ans=ans%MOD;
for(int i = 0; i < temp.size(); i++)
{
cout << temp[i] ;
}
cout<< endl;
}
return;
}
if (wine == 0) return;
temp.push_back('0');
backTrack( nn, mm + 1, wine - 1);
temp.pop_back();
temp.push_back('1');
backTrack( nn + 1, mm, wine * 2);
temp.pop_back();
}
int main() {
n=3;
m=10;
cin >> n >> m;
backTrack( 0, 0, 2);
cout << ans << endl;
return 0;
}
*/
