sto provando a risolvere treni ho pensato di utilizzare una ricorsione e come ho visto fare per altri problemi memorizzare i vari scenari cosi da non dover ricalcolare continuamente le stesse cose, tutto ciò funziona fino al 3 subtask, nel 4 i primi 2 mi da output errato e da li in poi fa timed out non ho piu idee su come risolvere
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
// Funzione ricorsiva per calcolare il massimo tempo possibile con memoizzazione
int dp(int i, int h, bool v, int N, int a[], int b[], unordered_map<int, int>& memo) {
// Calcoliamo l'hash univoco per ogni stato i, h, v
int state = (i * 2 + (v ? 1 : 0)) * 10000 + h;
// Se abbiamo già calcolato questo stato, restituiamo il valore memorizzato
if (memo.find(state) != memo.end()) {
return memo[state];
}
// Se abbiamo raggiunto la fine dell'array, restituiamo il tempo accumulato
if (i == N) {
return h;
}
// Calcoliamo il risultato scegliendo di non aggiungere nulla in questa iterazione
int result = dp(i + 1, h, false, N, a, b, memo);
result = max(result, dp(i + 1, h + a[i], true, N, a, b, memo));
if (!v) {
result = max(result, dp(i + 1, h + b[i], true, N, a, b, memo));
}
// Memorizziamo il risultato per evitare calcoli ripetuti in futuro
memo[state] = result;
return result;
}
int tempo_massimo(int N, int a[], int b[]) {
unordered_map<int, int> memo;
return dp(0, 0, false, N, a, b, memo);
}