AcWing 4408. 李白打酒加强版
原题链接
中等
作者:
CqAq
,
2024-04-07 22:06:39
,
所有人可见
,
阅读 2
算法1
C++ 代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define inf 1000000007
int n, m;
const int N = 110;
ll f[N][N][N + 4];//简单定义
//表示在遇到第i家店,第j朵花之后剩余酒量为w的方案数
//本题最后求出f[n][m - 1][1],n家店之后还剩最后一朵花,且还剩1斗酒
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> m;
//简单判断一下边界就可以
f[0][0][2] = 1;
for(int i = 0; i <= n; ++ i)
for(int j = 0; j <= m; ++ j)
for(int w = 0; w <= m; ++ w){
if(i && w % 2 == 0) f[i][j][w] = (f[i][j][w] + f[i - 1][j][w / 2]) % inf;
if(j) f[i][j][w] = (f[i][j][w] + f[i][j - 1][w + 1]) % inf;
}
cout << f[n][m - 1][1];
return 0;
}