【2022年省赛B组】试题I: 李白打酒加强版

题解

由于$N,M$的最大值为100，要满足题目要求——在最后一次将酒喝完，则说明就得上限不会超过$M$。总共存在$N+M$次相遇，每次相遇存在两种可能性，如果暴力枚举所有可能性，时间复杂度为$2^{N+M}$， 则无法通过。 每次相遇存在两种情况，最终需要经过$N$次店，$M$次花，这个约束和背包问题很类似。考虑能否使用动态规划进行优化。 在背包问题中，每件物品存在"取"和"不取"两种可能，取之后根据物品的体积和价值进行更新。 此处对应着相遇是否为“店”和“花”：

• 如果是花，则花的数量+1， 酒-1；
• 如果是店，则店的数量+1， 酒$\times 2$。 因此定义$dp[i][j][k]$表示第$i$次相遇，每次相遇需要维护店的数量$j$(或者花的数量$i - j$, 维护其中一个即可)。酒量为$k$的方案数。

题目要求的是“遇到店$N$次，遇到花$M$次， 最后一次遇到的是花，正好把酒喝光”的方案数。也就相当于在前$N+M-1$次中，遇到店$N$次， 酒量为1的方案数$(dp[N+M-1][N][1])$,因为此时最后遇到花才能恰好喝完。

接下来考虑$dp$数组的动态转移方程：

• 初始时从家中出来有2斗酒，可以表示为边界情况$dp[0][0][2] = 1$；
• 如果第$i$次相遇为花，则$dp[i][j][k]$可以由$dp[i-1][j][k + 1]$转移过来，相当于前$i - 1$次相遇中遇到店铺为$j$次、酒量为$k + 1$, 第$i$次为花则店铺数量不变，酒量数量减一；
• 如果第$i$次相遇为店，则$dp[i][j][k]$中的$k$必须为偶数，此时从$dp[i - 1][j - 1][k / 2]$转移过来。 根据上述分析，可以根据$k$的奇偶性和转移方程更新$dp$数组。 实现时注意防止计算溢出。

提交代码

#include<bits/stdc++.h>
#define int long long
const int N = 100 + 10, mod = 1e9 + 7;
int dp[2 * N][N][N];

void solve()
{
    int n, m; std::cin >> n >> m;
    
    
    dp[0][0][2] = 1;
    for(int i = 1; i <= n + m - 1; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            for(int k = 0; k <= m; k++)
            {
                if(k % 2 == 0 && j)
                {
                    dp[i][j][k] = (dp[i - 1][j][k + 1] + dp[i - 1][j - 1][k / 2]) % mod;
                }
                else
                {
                    dp[i][j][k] = dp[i - 1][j][k + 1];
                }
            }
        }
    }
    
    std::cout << dp[n + m - 1][n][1] << "\n";
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t = 1;
    while(t--) solve();
    return 0;
}