第十三届蓝桥杯 2022年4月 省赛 CC++ B组 I 题 李白打酒加强版 题解 DP

I 李白打酒加强版 (25分) 【问题描述】

话说大诗人李白，一生好饮。

幸好他从不开车。

一天，他提着酒壶，从家里出来，酒壶中有酒 2 22 斗。

他边走边唱：
无事街上走，提壶去打酒。

逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店 N NN 次，遇到花 M MM 次。

已知最后一次遇到的是花，他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？
注意：壶里没酒( 0 00 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。

【输入格式】

第一行包含两个整数 N NN 和 M MM.

【输出格式】

输出一个整数表示答案。

由于答案可能很大，输出模 1000000007 10000000071000000007 的结果。

【样例输入】

5 10
1

【样例输出】

14
1

【样例说明】

如果我们用 0 00 代表遇到花，1 11 代表遇到店，14 1414 种顺序如下：
010101101000000 010101101000000010101101000000
010110010010000 010110010010000010110010010000
011000110010000 011000110010000011000110010000
100010110010000 100010110010000100010110010000
011001000110000 011001000110000011001000110000
100011000110000 100011000110000100011000110000
100100010110000 100100010110000100100010110000
010110100000100 010110100000100010110100000100
011001001000100 011001001000100011001001000100
100011001000100 100011001000100100011001000100
100100011000100 100100011000100100100011000100
011010000010100 011010000010100011010000010100
100100100010100 100100100010100100100100010100
101000001010100 101000001010100101000001010100

【评测用例规模与约定】

对于 40 % 40%40% 的评测用例：1 ≤ N , M ≤ 10 1 ≤ N, M ≤ 101≤N,M≤10。

对于 100 % 100%100% 的评测用例：1 ≤ N , M ≤ 100 1 ≤ N, M ≤ 1001≤N,M≤100。

题解 DP

dp[i][j][k]表示遇到i个酒店和j朵花现在还剩k壶酒的所有路线数

只遇到酒店和只遇到花的情况需要初始化一下。

代码

#include
using namespace std;
const int mod = 1e9 + 7;
const int N = 110;
typedef long long ll;
ll dp[N][N][N];
int n, m;
#define ll long long
ll qm(int a, int b){
    int ans = 1;
    while(b) {
        if(b & 1) ans = ans * a ;     
        a = a * a ;                   
        b >>= 1;                         
    }
    return ans;
}
int main()
{
    cin >> n >> m;
    dp[0][0][2] = 1; //只遇到花
    dp[0][1][1] = 1; //只遇到花
    for(int i = 0; i <= 7 ; i ++ )
    {
        dp[i][0][qm(2, i + 1)] = 1; //初始化  将只遇到酒店的 初始化为1
    }
    for(int i = 1; i <= n; i  ++ )
        for(int j = 1; j <= m ; j ++ )
            for(int k = 0; k <= m; k ++  )
            {
                if(k % 2 == 0)
                dp[i][j][k] = (dp[i - 1][j][k / 2] + dp[i][j - 1][k + 1] ) % mod ; //遇到酒店 或者 遇到 花
                else 
                dp[i][j][k] = dp[i][j - 1][k + 1];  //只能遇到花

            }
    cout << dp[n][m - 1][1]  << endl;  
    return 0;
}

---

算法2 (暴力枚举) DFS 只能过两个样例

记住最后两次肯定都是花

代码

#include 
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;
int n, m;
ll sum = 0;

void  dfs(int x, int y, int s) {
    if (x == n && y == m - 2  && s == 2) {
        sum ++;
        sum = sum % mod;
    }
    if (x < n) dfs(x + 1, y, s * 2);
    if (s > 0 && y < m - 2) dfs(x, y + 1, s - 1);
}
int main() {
    cin >> n >> m;
    dfs(0, 0, 2);
    cout << sum << endl;
    return 0;
}