考察知识点:递归
递归求解:
- 当补给次数超过 3 次或当前糖果数量小于 0 时,返回。
- 当当前位置超过 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;
}