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]就一定为最后遇花的方案数
因为已知最后一次遇到的是花，他正好把酒喝光了，遇一次花喝一次酒，酒的数量枚举到和花一样多即可
#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;
}
