蓝桥杯2022年B组C/C++李白打酒加强版

链接

题意：在一条路上，分别有N个店，M个花。初始有2两酒，每遇到店酒翻一倍，每遇到花喝一两酒。

题解：记忆化搜索剪枝。一共有N+M个点，分别讨论该点是店和是花的情况。遇到不符合题意的递归回去，剪枝是为了减少时间复杂度。

下面是记忆化搜索的步骤

记忆化剪枝就是记录已经计算过的状态，不需要重新计算，节省时间。

代码 重要是怎么减，

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <math.h>
#include <string>
#define PI 3.14159
using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
const int MAX_INT = 0x3f3f3f3f;
const int N = 1e2 + 15;
const int mod = 1e9 + 7;
LL a[N][N][N];

LL dfs(int n, int m, int t)
{
    if (t == 0)
        return (n == 0 && m == 0); //没酒遇见花
    if (t > m || n >= m)
        return 0; //剩余酒的数量大于花的 或 剩余的客栈大于花
    if (n == 0)//不存在店时，讨论花的数量和酒的数量是否一样
        return m == t;

    if (a[n][m][t] != -1)
        return a[n][m][t]; //记忆化搜索
    LL ans = dfs(n, m - 1, t - 1) + dfs(n - 1, m, t + t);
    ans %= mod;
    a[n][m][t] = ans;
    return ans;
}

void solve()
{
    memset(a, -1, sizeof a);
    int n, m;
    cin >> n >> m;
    cout << dfs(n, m, 2) << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    while (T--)
    {
        solve();
    }
}