Tävlingsprogrammering/Uppgifter/Plocka Äpllen
Rekursion. Blir väldigt mycket snabbare om man inser att man aldrig behöver gå tillbaka utan endast upp/ner/höger.
Lösning av Andreas Wallström:
#include <iostream>
#include <algorithm>
using namespace std;
typedef vector<vector<int>> vvi;
int recur(int x, int y, int k, vvi apples);
int N, K;
int main() {
cin >> N >> K;
vector<vector<int>> apples(2, vector<int>(N));
for(int i = 0; i < N; ++i) cin >> apples[0][i];
for(int i = 0; i < N; ++i) cin >> apples[1][i];
cout << recur(0, 1, K, apples) << endl;
}
int recur(int x, int y, int k, vvi apples) {
//Out of bounds
if(x < 0 || x >= N || y < 0 || y > 1)
return -1;
--k;
int applesTaken = apples[y][x];
apples[y][x] = 0;
if(k == 0)
return applesTaken;
int best;
best = recur(x, y-1, k, apples);
best = max(best, recur(x+1, y, k, apples));
best = max(best, recur(x, y+1, k, apples));
return applesTaken + best;
}