通过题目描述,我们可以知道这道题目涉及到某种状态时候的方案数,因此我们可以用动态规划来解决问题,并且我们需要注意到酒的状态,因此我们可以用三维数组来存储状态,我们知道N,M最大不会超过100,并且如果酒超过了100斗,即使遇到100朵花也无法喝完,因此只需要定义大小都为100的三维数组即可,并且枚举三种状态,分别是店家,遇到的花以及酒的斗数都进行枚举,根据状态转移方程求得每个状态的方案数量,并且初始化动态数组dp[0][0][2] = 1;因为最后遇到的肯定是花,因此我们只需要输出倒数第二个状态,也就是dp[n][m - 1][1]即可
上代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e2 + 10, mod = 1e9 + 7;
int dp[N][N][N];//dp[i][j][k]表示遇到i个店,j朵花,剩下k斗酒的方案
//当dp[i][j - 1][1]的时候就是答案,因为最后一次肯定是遇到花,并且正好喝完
//需要注意的是,最多遇到的花是100朵此时如果酒多于100斗就相当于答案无效,因为喝不完
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
dp[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++){
//因为上一次从店家出来,因此此时k为偶数,并且i >= 1才可以进行
if(k % 2 == 0 && i) dp[i][j][k] = (dp[i - 1][j][k / 2] + dp[i][j][k]) % mod;
//上一次遇到了花,因此上一次的状态是k + 1
if(j) dp[i][j][k] = (dp[i][j - 1][k + 1] + dp[i][j][k]) % mod;
}
}
}
cout << dp[n][m - 1][1] << endl;//最后只需要输出dp[n][m][1]的方案即可
return 0;
}