洛谷 p8786. [蓝桥杯 2022 省 B] 李白打酒加强版
原题链接
中等
作者:
y总的小迷弟
,
2023-10-01 19:41:26
,
所有人可见
,
阅读 65
//数据范围比较小,考多维dp
//考虑设f[i][j][k]为经过i家店,遇到j朵花时,有k斗酒的方案数;
//不难得到状态转移方程:f[i][j][k] += f[i][j][k] += f[i - 1][j][k / 2] + f[i][j - 1][k+1];(前者要满足k%2==0)
//一些小细节要注意;
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int n, m;
int f[110][110][110];
int main()
{
cin >> n >> m;
f[0][0][2] = 1;
//初始化,刚开始有两斗酒
for(int i = 0;i <= n;i++)//从0开始,因为有可能没遇店就遇花;
{
for(int j = 0;j <= m;j++)//从0开始,因为有可能没遇花就遇店;
{
if(!i && !j)
continue;
for(int k = 0;k <= m;k++)//为什么酒的上限是m?因为大于m的话酒必定喝不完;
{
if(k % 2 == 0 && i)
f[i][j][k] += f[i - 1][j][k / 2];
if(j && k + 1 <= m)
f[i][j][k] += f[i][j - 1][k + 1];
f[i][j][k] %= mod;
}
}
}
cout << f[n][m - 1][1] << endl;//由于最后一次一定遇花,所以时这个状态;
return 0;
}