//纯纯暴搜,毫无剪枝(蓝桥云课:4/10)
#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
int ans;
void dfs(int cnt, int v, int n, int m)
{
if(cnt == 1)
{
if(m == 1 && v == 1) ans ++;
return;
}
if(n > 0) dfs(cnt - 1, v * 2, n - 1, m);
if(m > 1) dfs(cnt - 1, v - 1, n, m - 1);
}
int main()
{
cin >> n >> m;
int cnt = n + m;
int v = 2;
dfs(cnt, v, n, m);
cout << ans << endl;
return 0;
}
----------------------------------------------------
//在暴搜的基础上加了一步剪枝:
//当酒壶里的酒大于剩下花的数目时,直接返回上一层
//但好想AC的数量还是(蓝桥云课4/10)/(T...T)\
#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
int ans;
void dfs(int cnt, int v, int n, int m)
{
if(cnt == 1)
{
if(m == 1 && v == 1) ans ++;
return;
}
if(v > m) return;//剪枝优化
if(n > 0) dfs(cnt - 1, v * 2, n - 1, m);
if(m > 1) dfs(cnt - 1, v - 1, n, m - 1);
}
int main()
{
cin >> n >> m;
int cnt = n + m;
int v = 2;
dfs(cnt, v, n, m);
cout << ans << endl;
return 0;
}
----------------------------------------------------
//DP方法,类似数字三角形的DP问题,即可按算法提高课归类为“数字三角形”类DP问题
//DP问题其实只要构造出合适的状态表示,就成功一大半了,因为DP问题在代码上不是很难
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110, mod = 1000000007;
//状态表示——f[i][j][k]:已经经过i家店,j朵花且壶里恰有k个单位的酒的方案数,其值表示方案的个数
//状态计算:将状态表示的集合划分成两个子集A,B,A子集表示最后经过的是店,B子集表示最后经过的是花
// 则f[i][j][k] = f[i - 1][j][k / 2] + f[i][j - 1][k + 1];
int n, m;
int f[N][N][N];
int 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 ++)
{
int &v = f[i][j][k];
if(i >= 1 && k % 2 == 0) v = (v + f[i - 1][j][k / 2]) % mod;
if(j >= 1) v = (v + f[i][j - 1][k + 1]) % mod;
}
cout << f[n][m - 1][1] << endl;
return 0;
}