Ciao a tutti, stavo provando a risolvere il problema “troupe televisive”, tuttavia, a parte una soluzione in DP con complessità N^3 (che totalizza 35/100), non saprei in che altro modo approcciare il problema. Qualcuno può darmi qualche indizio?
Quale è l’idea del tuo algoritmo attuale?
1 Mi Piace
Creo una matrice tridimensionale, dove M[a][b][c] è la soluzione ottimale per le riprese dalla numero c fino alla numero N avendo le fotocamere in a e in b. Sostanzialmente ogni volta, con una funzione ricorsiva, provo a muovere l’una o l’altra telecamera per riprendere l’evento c+1, salvando la soluzione ottima delle due. Per ricorstruire la sequenza poi faccio backtracking
Il codice è un po’ troppo disordinato, quindi forse confonde solo le idee
Sei sicuro che ti servano tutte e 3 le informazioni che memorizzi?
Oppure alcune le puoi ricavare dalle altre?
2 Mi Piace
in effetti, se conosco i movimenti di una delle due troupe posso ricavare quelli dell’altra, tuttavia non so come questo possa essere utilizzato per ottimizzare la dp
Per ogni evento, escluso il primo, la posizione di una delle 2 telecamere sarà uguale alla posizione che aveva nell’evento precedente, quindi puoi evitare di memorizzarla.
1 Mi Piace
In che modo? A priori non posso sapere quale delle due telecamere si muoverà
Se l’ultimo evento che stato ripreso è l’i-esimo, puoi dedurre la posizione di almeno una delle due troupe? 
1 Mi Piace
Si, avrò che o la telecamera x è in posizione X[i], o che la telecamera Y è in posizione Y[i]. Tuttavia, non posso sapere in quale dei due casi mi trovo
Aggiungi una terza dimensione per saperlo, tale dimensione serve per capire se il valore contenuto nella seconda dimensione(quello della telecamera che è rimasta ferma) si riferisce R O F,
1 Mi Piace
Chiedo scusa per non aver risposto in precedenza, grazie mille dell’aiuto, ora dovrei averlo risolto.