1.李白打酒加强版

1.题目描述

话说大诗人李白, 一生好饮。幸好他从不开车。

一天, 他提着酒壶, 从家里出来, 酒壶中有酒 2 斗。他边走边唱:

无事街上走，提壶去打酒。 逢店加一倍, 遇花喝一斗。

这一路上, 他一共遇到店 $N$ 次, 遇到花 $M$ 次。已知最后一次遇到的是花，他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?

注意: 壶里没酒 ( 0 斗) 时遇店是合法的, 加倍后还是没酒; 但是没酒时遇 花是不合法的。

2.输入格式

5 10

3.输出格式

14

4.样例说明

如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：

010101101000000

010110010010000

011000110010000

100010110010000

011001000110000

100011000110000

100100010110000

010110100000100

011001001000100

100011001000100

100100011000100

011010000010100

100100100010100

101000001010100

5.数据规模

$1\le N,M\le 100$

6.原题链接

李白打酒加强版

2.解题思路

比较明显是一道状态机dp的题目，如何定义好状态可以帮助我们更好地初始化和转移以及求解答案，根据题目范围最大为100，比较明显暗示我们做法是一个$O(n^3)$的dp，dp状态也应该是三维的。定义状态$f[i][j][k]$ 为已经遇到 $i$ 次店，$j$次花，还剩 $k$ 斗酒的方案数。状态初始化明显是f[0][0][2]=1。

对于酒的上限数量，我们应该想好范围，因为花最多只有 $m$ 朵，意味着我们最多只能喝 $m$ 壶酒，对于 $k$ 超过 $m$ 的状态都是无效状态我们无需关心。所以剩余酒的上限也就是 $k$ 应该也定为 $m$ 。

考虑进行状态转移，对于状态$f[i][j][k]$，假设最后一次遇到的是店，那么此时需要保证 $i$ 大于0，并且 $k$ 是偶数，因为遇到店剩余酒翻倍，$k$ 一定不可能为奇数，那么可以得到转移方程
$$f[i][j][k]=(f[i][j][k]+f[i-1][j][k/2])\%mod$$

假设最后一次遇到的是花，那么此时只需要保证 $j$ 大于 0即可，我们可以获得转移方程$$f[i][j][k]=(f[i][j][k]+f[i][j-1][k+1])\%mod$$

我们还得考虑答案输出什么，题目要求最后一次遇到的必须是花，那么我们直接输出 $f[n][m][0]$ 肯定是错误的答案。 因为这并不能保证最后一次遇到的是花，因为最后是0壶酒，那么在遇到最后一朵花时应该还剩1壶酒，所以我们可以输出 $f[n][m-1][1]$ 作为答案。

3.Ac_code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 110;


int n, m;
//已经遇到i次店,j次花,还剩k斗酒的方案数
LL f[N][N][N];
void solve()
{
    cin >> n >> m;
    f[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 && k % 2 == 0) f[i][j][k] = (f[i][j][k] + f[i - 1][j][k / 2]) % mod;
                //最后一次遇到花
                if (j) f[i][j][k] = (f[i][j][k] + f[i][j - 1][k + 1]) % mod;
            }
        }
    }
    cout << f[n][m - 1][1] << '\n';
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}