[蓝桥杯 2022 省 B] 李白打酒加强版

本文主要是介绍[蓝桥杯 2022 省 B] 李白打酒加强版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

[蓝桥杯 2022 省 B] 李白打酒加强版

题目描述

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

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

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

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

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

注意：壶里没酒（ $0$ 斗）时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。

输入格式

第一行包含两个整数 $N$ 和 $M$ 。

输出格式

输出一个整数表示答案。由于答案可能很大，输出模 $1000000007$ （即 $10^7 + 7$ ) 的结果。

输入输出样例

输入

5 10

输出

数据范围

$\leq n, m \leq 100$

解法：动态规划

我们定义 $f (i, j, k)$ 为遇到店 $i$ 次，遇到花 $j$ 次，酒壶里有 $k$ 斗酒的方案数。

我们最终要返回的是遇到店 $n$ 次，遇到花 $m$ 次 且最后一次遇到的是花，酒壶里有 $0$ 斗酒的方案数。

实际上，它等价于遇到店 $n$ 次，遇到花 $m - 1$ 次，酒壶里有 $1$ 斗酒的方案数。因为这样保证了最后一次是遇到花的，两者实际等价，即 $f (n, m - 1, 1)$ 。

由于 $m$ 不超过 $100$ ，那么 $k$ 也不超过 $100$ ，否则喝不完酒。

我们直接讨论当前遇到的是店，还是花：

如果当前遇到的是店，那么 $f [i] [j] [k] = f [i] [j] [k] + f [i - 1] [j] [k /2]$ ，这里需要保证 $i > 0$ 且 $\ mod\ 2 = 0$ ；
如果当前遇到的是花，那么 $f [i] [j] [k] = f [i] [j] [k] + f [i] [j - 1] [k + 1]$ ，这里需要保证 $j > 0$ ；

初始 $f [0] [0] [2] = 1$ ，表示最开始酒壶里有 $2$ 斗酒。

最终返回的答案就是 $f [n] [m - 1] [1]$ 。

时间复杂度： $\times m \times k)$

C++代码：

#include <iostream>
#include <cstring>
#include <vector>
#include <functional>
#include <unordered_set>
#include <set>
#include <algorithm>using namespace std;
using LL = long long;const int MOD = 1e9 + 7;
const int N = 110;LL f[N][N][N];void solve(){int n, m;cin>>n>>m;f[0][0][2] = 1;for(int i = 0;i <= n;i++){for(int j = 0;j < m;j++){if(i == 0 && j == 0) continue; for(int k = 0;k <= 100;k++){if(k % 2 == 0 && i) f[i][j][k] += f[i - 1][j][k / 2];//操作1if(j)               f[i][j][k] += f[i][j - 1][k + 1];//操作2f[i][j][k] %= MOD;}}}cout<<f[n][m - 1][1];
}int main(){int t = 1;//cin>>t;while(t--){solve();}return 0;
}

Java代码：

import java.util.*;
import java.io.*;public class Main
{static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));static final int N = 110;static final int MOD = 1000_000_007;public static void main(String[] args) throws Exception{String[] strs = reader.readLine().split(" ");int n = Integer.parseInt(strs[0]);int m = Integer.parseInt(strs[1]);int[][][] f = new int[N][N][N];f[0][0][2] = 1;for(int i = 0;i <= n;i++){for(int j = 0;j <= m;j++){if(i == 0 && j == 0) continue;for(int k = 0;k <= 100;k++){if(k % 2 == 0 && i > 0) f[i][j][k] += f[i - 1][j][k / 2];if(j > 0)               f[i][j][k] += f[i][j - 1][k + 1];f[i][j][k] %= MOD;}}}System.out.println(f[n][m - 1][1]);}
}