# Aiuto Treni(20/100)

**URL:** <https://forum.olinfo.it/t/aiuto-treni-20-100/8945>\
**Category:** Aiuto\
**Created:** [27 Giugno 2024, 9:19am UTC](https://forum.olinfo.it/t/aiuto-treni-20-100/8945 "2024-06-27T09:19:37Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![GiacomocCol](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/919ad9/32.png) [@GiacomocCol](https://forum.olinfo.it/u/GiacomocCol)\
**Post date:** [27 Giugno 2024, 9:19am UTC](https://forum.olinfo.it/t/aiuto-treni-20-100/8945/1 "2024-06-27T09:19:38Z")

</div>

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

```auto
#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);
}

```

---

<div class="post-metadata">

**Author:** ![TizioGrigio0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/tiziogrigio0/32/1819_2.png) [@TizioGrigio0](https://forum.olinfo.it/u/TizioGrigio0)\
**Post date:** [27 Giugno 2024, 8:27pm UTC](https://forum.olinfo.it/t/aiuto-treni-20-100/8945/2 "2024-06-27T20:27:26Z")

</div>

Ti stai rendendo la vita difficile, è possibile risolvere il problema utilizzando un singolo ciclo for che viene ripetuto N volte.  
La soluzione che io ho trovato (che non sono neanche sicuro sia l’unica) non è proprio facile da intuire, ma in poche righe riesce a funzionare ciclando una volta.

Indizio: per far funzionare il metodo che io ho usato è necessario conservare un numero dal ciclo precedente e sottrarlo a un altro valore di cui sei gia in possesso.