第十三届蓝桥杯C++B组省赛 I 题——李白打酒加强版（AC）

妖狐艹你老母 2023-09-28 23:25 32阅读 0赞

#### 目录 ####

*  1.李白打酒加强版
 *   *  1.题目描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例说明
     *  5.数据规模
     *  6.原题链接
 *  2.解题思路
 *  3.Ac\_code

## 1.李白打酒加强版 ##

### 1.题目描述 ###

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

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

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

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

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

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

### 2.输入格式 ###

5 10

### 3.输出格式 ###

### 4.样例说明 ###

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

010101101000000

010110010010000

011000110010000

100010110010000

011001000110000

100011000110000

100100010110000

010110100000100

011001001000100

100011001000100

100100011000100

011010000010100

100100100010100

101000001010100

### 5.数据规模 ###

1 ≤ N , M ≤ 100 1≤N,M≤100 1≤N,M≤100

### 6.原题链接 ###

[李白打酒加强版][Link 1]

## 2.解题思路 ##

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

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

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

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

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

[Link 1]: https://www.lanqiao.cn/problems/2114/learning/