深圳公安门户网站免费友情链接平台

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;
}