Ciao a tutti!
Pensando al problema, non mi sembra ci possa essere un modo facile di prevedere qual’è la scelta di carte da fare in un dato istante, quindi l’ho risolto tramite back-tracking.
Il codice:
int solve(int N, int K, vector<vector<int>> decks, int max_pick) {
int res = 0;
for (vector<int> &deck: decks) {
if (deck.empty()) {
continue;
}
int last_element = deck.back();
deck.pop_back();
if (last_element > max_pick) {
res = max(res, 1 + solve(N, K, decks, last_element));
} else {
res = max(res, solve(N, K, decks, max_pick));
}
deck.push_back(last_element);
}
return res;
}
int gioca(int N, int K, vector<vector<int>> decks) {
for (vector<int> &deck: decks) {
reverse(deck.begin(), deck.end());
}
return solve(N, K, decks, 0);
}
Ho invertito i vettori, solo per poter aggiungere/togliere dalla fine un elemento senza dover shiftare tutto il vettore.
A parte i primi 3 test, ottengo solo:
Execution killed (could be triggered by violating memory limits)
Immagino perché la chain-call sia troppo lunga…
Se già così fallisce i test per i limiti di memoria, immagino che aggiungere la memoizzazione non sia la strada giusta.
Vi chiedo un consiglio su come rivedere la soluzione.
Del pruning basterebbe?