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

题目链接

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

题目描述

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

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

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

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

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

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

输入格式

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

输出格式

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

输入输出样例

输入

5 10

输出

14

数据范围

• $1\le n,m\le 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$ 且 $kmod2=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]$。

时间复杂度：$O(n\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]);}
}