Ciao ragazzi qualcuno potrebbe inviarmi il quarto esercizio delle territoriali (quello da 24 punti)
Ciao! Non ho partecipato alle territoriali, ma dovrei avere la soluzione.
L’idea è una programmazione dinamica in cui ti salvi il minimo costo per ogni configurazione degli ultimi due elementi (quindi 2^2 configurazioni).
Sia f(i, mask) il minimo costo per prendere i primi i elementi in modo tale che le ultime due scelte siano i bit di mask, ad esempio 01 \to sx,dx.
f(i+1, 00_2) = cost(i+1, 0) + f(i, 10_2)
f(i+1, 01_2) = cost(i+1, 1) + min(f(i, 00_2),f(i, 10_2))
e così via, evitando sempre 000 e 111, come richiede il testo.
Ci sono 4 mask per ogni indice, quindi \mathcal{O}(n) stati. Per calcolare ogni stato ci metto \mathcal{O}(1), quindi la complessità finale è \mathcal{O}(n), sia come tempo che come memoria.
1 Mi Piace
Grazie mille
Bella soluzione, sfortunatamente la soluzione che ho fatto io mi ha permesso di ottenere solo 11/24, io avevo pensato semplicemente a una sorta di ricorsione con memoization per ottenere il risultato ottimale
