Ciao a tutti,
chiedo (disperatamente) aiuto per risolvere questo problema. Ho provato a leggere il booklet con le soluzioni ma di quella ottimale ci ho capito poco o niente (in precedenza ero riuscito ad implementare, seppur con qualche imperfezione, la soluzione non ottimale che fa uso della ricerca binaria).
Ciao, io per risolvere il problema ho considerato questo: è inutile scegliere di percorrere una passerella lunga P se andando avanti percorrendo un tratto di strada lungo S si trova un’altra passerella lunga P1 tale che P>S+P1.
Prova a fare un disegnino per capirlo.
Spero di esserti stato d’aiuto.
Sisi, quello l’ho capito…
Però, nella soluzione del booklet si parte dal fondo e per ogni passerella si fa questo ragionamento:
- prima elimino tutte le passerelle successive tali che P[u+1] -D[u+1] > P[u] - D[u] , e fin qui ci siamo, se devo entrare in una determinata passerella successiva tanto vale farlo da quella che mi implica un percorso minore in uscita
- poi aggiungo la passerella esaminata solo se P[u] + D[u] < P[u+1] + D[u+1], cioè (se ho capito bene) solo se il percorso in entrata della nuova passerella è minore di quello della successiva… è questo punto che non capisco, cosa mi assicura che questa sia la soluzione migliore?
Allora, io onestamente non mi sono affidato al booklet né ho studiato la soluzione che proponeva ma credo che l’idea di base di entrambe le soluzioni sia la seguente: vale la pena imboccare una passerella se e solo se ciò è conveniente sia in entrata e in uscita.
Mi spiego meglio: se a un certo punto imboccassimo una passerella perché la sua lunghezza P è minore di quella che ci toccherebbe percorrere se provassimo a raggiungere una qualsiasi altra spiaggia (o la fine della strada) la cosa potrebbe essere conveniente, MA, se scoprissimo che la strada che dovremmo fare per percorrere la passerella per tornare alla strada fosse è maggiore di quella che abbiamo percorso dall’ultima spiaggia dove siamo stati (o dall’inizio della strada) per arrivare al punto dove abbiamo imboccato questa nuova passerella allora ci renderemmo conto che avremmo fatto un errore e che questa passerella sarebbe dovuta essere evitata.
Spero che adesso ti sia più chiaro il problema.
Ti ringrazio per il chiarimento, proverò a ragionarci un po’ sopra