25 lines
790 B
C++
25 lines
790 B
C++
// lanqiao 2114 李白打酒加强版 (记忆化搜索)
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 1e2 + 10, mod = 1e9 + 7;
|
|
int f[N][N][N];
|
|
int dfs(int s, int cur_n, int cur_m){
|
|
// 非法
|
|
if(s < 0 || cur_n < 0 || cur_m < 0) return 0;
|
|
// 优化1-可行性剪枝: 酒量大于剩余遇见花的次数无效
|
|
if(s > cur_m) return 0;
|
|
if(cur_m == 1 && cur_n == 0 && s == 1) return 1;
|
|
// 优化2-记忆化搜索
|
|
if(f[s][cur_n][cur_m] != -1) return f[s][cur_n][cur_m];
|
|
f[s][cur_n][cur_m] = (dfs(s*2, cur_n - 1, cur_m) + dfs(s - 1, cur_n, cur_m - 1)) % mod;
|
|
return f[s][cur_n][cur_m];
|
|
}
|
|
int main(){
|
|
fill(f[0][0], f[0][0] + N*N*N, -1);
|
|
int n, m; cin >> n >> m;
|
|
cout << dfs(2, n, m) << endl;
|
|
return 0;
|
|
}
|
|
/* test samples -> 14
|
|
5 10
|
|
*/ |