题解 | #iko和她的糖#

考察知识点：递归

递归求解：

• 当补给次数超过 3 次或当前糖果数量小于 0 时，返回。
• 当当前位置超过 n 时，更新答案并返回。

时间复杂度：$O(2^n)O(2^n)$ + 剪枝

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define N 1005
int a[N], b[N], ans = 0, n;
bool flag = true;

void dfs(int pos, int tang, int k)  // pos: 当前位置，tang: 当前糖果数量，k: 补给次数
{
    if (k > 3)
        return;
    else if (tang < 0)
        return;
    else if (pos > n)
    {
        flag = false;
        ans = max(ans, tang);
        return;
    }
    dfs(pos + 1, tang + a[pos] - b[pos], k + 1);
    dfs(pos + 1, tang - b[pos], k);
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i < n; ++i)
        cin >> b[i];
    dfs(1, 0, 0);
    if (flag)
        cout << -1 << endl;
    else
        cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}