Puoi leggere e provare a risolvere il problema visitando la piattaforma Terry.
Per risolvere l'esercizio torna molto utile essere familiari con la tecnica della programmazione dinamica.
Il cuore della programmazione dinamica sta nel cercare di calcolare la soluzione ottima al problema utilizzando le soluzioni ottime di versioni più "piccole" dello stesso problema. Questa scomposizione si può fare in modo iterativo ("bottom up") oppure ricorsivo ("top down"). Entrambi i modi vanno bene, ti consigliamo di imparare entrambi ma va bene utilizzare quello che ti viene più comodo.
Prendiamo uno dei casi d'esempio proposti dal problema:
5
1 4
1 4
4 5
1 4
3 2
Proviamo a costruire la soluzione ottima all'intero problema partendo dalla soluzione ottima del problema che ha solo la prima fila di finestrini (1 4). La soluzione per (1 4) naturalmente è 1, data dal minimo tra 1 e 4.
Proviamo a estendere la soluzione per (1 4) aggiungendo la fila successiva, anch'essa (1 4). Notiamo che anche in questo caso possiamo scegliere il finestrino di costo minore (1) pagando quindi un totale di .
Nel momento in cui arriviamo alla terza fila, non ci basta più conoscere la soluzione migliore per le due file precedenti (di valore 2) dato che non possiamo estenderla a nostro piacimento: dobbiamo evitare tre finestrini aperti consecutivamente dallo stesso lato!
Dobbiamo quindi considerare quattro possibili soluzioni, per ogni sottoproblema:
Conoscendo queste 4 soluzioni per ogni sottoproblema, possiamo estenderle e calcolare le quattro soluzioni per il sottoproblema di dimensione più grande:
Implementata nel modo descritto, la soluzione ha complessità .
t = int(input())
for i in range(t):
input()
n = int(input())
LL, LR, RL, RR = 0, 0, 0, 0
for j in range(n):
L, R = map(int, input().split())
# Questo assegnamento ci garantisce che vengono usati i valori vecchi
# prima di essere sovrascritti, e l'assegnamento avviene solo alla fine
LL, LR, RL, RR = (
RL + L,
min(LL, RL) + R,
min(LR, RR) + L,
LR + R,
)
print(f"Case #{i + 1}: {min(LL, LR, RL, RR)}")