4408. 李白打酒加强版 - AcWing题库
题目描述
题目分析
对于这题我们发现有三个变量,店,花,酒的数量,对于这种范围我们使用DP来进行分析。
dp[i][j][k]我们表示有i个店,j朵花,k单位酒的集合,其属性为数量
我们需要不重不漏将此分为两类进行dp,
第二类为最后是店dp[i - 1][j][k / 2]
条件:i >= 1(因为如果当前店数为0,之前一定没有遇过店,-1为负也不正确)
k % 2 == 0 (k可以被2整除,因为遇到店前必须为2的倍数才能/2)
第一类为最后是花dp[i][j - 1][k + 1]
条件:j >= 1 (同理)(k + 1遇花可以使其-1变成k)
注:最后输出时不能是dp[n][m][0],因为这样不能分清楚最后是遇花还是遇店,而且这样算无论遇花还是遇店的方案数都是一样的,所以输出dp[n][m - 1][1]就一定为最后遇花的方案数文章来源:https://www.uudwc.com/A/jrzO8/
因为已知最后一次遇到的是花,他正好把酒喝光了,遇一次花喝一次酒,酒的数量枚举到和花一样多即可文章来源地址https://www.uudwc.com/A/jrzO8/
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
const int N = 101;
int n, m, dp[N][N][N];
int main()
{
cin >> n >> m;
dp[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)//遇店
{
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k / 2]) % mod;
}
if(j >= 1)//遇花
{
dp[i][j][k] = (dp[i][j][k] + dp[i][j - 1][k + 1]) % mod;
}
}
}
}
cout << dp[n][m - 1][1];
return 0;
}