李白打酒加强版
题目描述
话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店 N 次，遇到花 M 次。
已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？
注意：壶里没酒( 0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。
输入格式
输入包含多组测试数据。
第一行为T，表示存在T组测试数据，T不超过30。
对于每组测试数据，输入两个整数N 和M.
1 ≤ N, M ≤ 100。
输出格式
输出一个整数表示答案。由于答案可能很大，输出模1000000007 的结果。
输入样例
5 10
输出样例
14
动态规划dp
思路：a[i][j][k]表示走到了第i家店，遇到了j朵花，酒的数量为k，然后就可以转移了
- f(i - 1, j, k / 2):遇到的是店，说明此前遇到店的数量为i - 1，遇到花的数量仍然为j，酒壶中酒的数量为k/2;满足条件i大于等于1，k能被二整除
- f(i, j - 1, k + 1):遇到的是花，说明此前遇到店的数量为i，遇到花的数量为j - 1，酒壶中酒的数量为k + 1。满足条件j大于等于1
注意转移的条件，然后i和j要从0开始遍历，还有结果是
a[n][m-1][1]才能保证最后一个是花且刚好酒为0
#include <bits/stdc++.h>
using namespace std;
int a[105][105][105];
const int MOD=1e9+7;
int main()
{
int n,m;
cin>>n>>m;
a[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>=1&&k%2==0) a[i][j][k]=(a[i][j][k]+a[i-1][j][k/2])%MOD;
if(j>=1) a[i][j][k]=(a[i][j][k]+a[i][j-1][k+1])%MOD;
}
}
}
cout<<a[n][m-1][1]<<endl;
return 0;
}