Ciao, qualcuno mi può dare qualche aiuto col problema torri? Non riesco proprio a partire.
Hai un problema di scelta: una certa torre posso scegliere se abbatterla o non abbatterla…
Prova a pensarla così! 
Ecco io avevo provato a ragionare in modo simile a questo.
Guardo se mi costa meno abbattere una certa torre o abbattere tutte quelle incompatibili con essa. Solo che non funziona. Allora ho provato a guardare le torri andando dalla più bassa alla più alta. Ma non funziona lo stesso. Infine ho provato ad accorpare insieme le torri che compaiono già in ordine di altezza (in quel caso si vede che o le tengo entrambe o le abbatto entrambe) ma anche questo non mi convince. Può essere pure che è più facile ma non mi rendo conto?
Prova a vedere il problema in termini di sottoproblemi: hai N torri, cosa puoi dire se conosci già la soluzione ottima per le prime N-1 torri?
Altro hint: invece di considerare il “costo minimo” per le torri abbattute, c’è un modo più furbo di pensare la soluzione… 
Avevo provato anche a considerare le prime N-1 torri. Se posso tenere pure l’n-esima insieme alla configurazione ottimale delle prime n-1 il problema è fatto. Però ci sono casi in cui per tenere l’n-esima devo abbattere quelle più basse che vengono prima e di conseguenza devo rialzare eventuali torri che avevo abbattuto e mi mordo la coda.
ci sono casi in cui per tenere l'n-esima devo abbattere quelle più basse che vengono prima e di conseguenza devo rialzare eventuali torri che avevo abbattutoE chi ti vieta di farlo? :pLuke
Immagina di essere davanti alla fila di torri: quali sono le scelte che posso prendere per la prima torre? Posso saperlo subito qual’è la scelta migliore per questa torre? E in ogni caso (qualunque scelta io faccia) una volta che mi trovo davanti alla seconda torre mi sono ridotto ad un problema simile a quello di partenza? 
(Ovviamente dipende dal tipo di implementazione) ma per questi problemi è sempre utile partire da una BruteForce e poi cercare di migliorarla!
Un po ci ho pensato ma vedo le stesse difficoltà che avevo all'inizio, perchè non posso sapere se tutte le torri siano rialzabili, e in che modo conviene rialzarleci sono casi in cui per tenere l'n-esima devo abbattere quelle più basse che vengono prima e di conseguenza devo rialzare eventuali torri che avevo abbattutoE chi ti vieta di farlo? :pLuke
cip999
Immagina di essere davanti alla fila di torri: quali sono le scelte che posso prendere per la prima torre? Posso saperlo subito qual'è la scelta migliore per questa torre? E in ogni caso (qualunque scelta io faccia) una volta che mi trovo davanti alla seconda torre mi sono ridotto ad un problema simile a quello di partenza? :PPer la prima domanda. Mi sa che non posso saperlo subito. Avevo trovato un caso in cui abbattere la prima torre costava meno che abbattere le torri che avrei dovuto abbattere per tenerla. Ma poi andando avanti quelle altre torri le ho dovute abbattere ugualmente e a quel punto conveniva tenere la prima torre. Quindi mi sa che non basta guardare solo la prima e vedere se costa di più tenerla o abbatterla.
(Ovviamente dipende dal tipo di implementazione) ma per questi problemi è sempre utile partire da una BruteForce e poi cercare di migliorarla!VashTheStampede
Per la seconda domanda. Si, con questo approccio si.
Sono curioso soprattutto perchè dai tempi dovrebbe essere un problema facile ma non ci riesco. Quindi penso che mi ostino a non vedere qualcosa di scontato.
Se può essere d’aiuto il problema è del tutto analogo a trovare la sequenza di torri decrescenti con il costo massimo.
Una volta trovata tale sequenza come ottengo la risposta al problema di partenza?
E’ equivalente visto il costo per l’abbattimento è dato dal costo totale meno quello delle torri in piedi, che quindi massimizzandolo minimizza quello per l’abbattimento. Ma non colgo il motivo profondo del perchè aiuta, cosa cambia?
E' equivalente visto il costo per l'abbattimento è dato dal costo totale meno quello delle torri in piedi, che quindi massimizzandolo minimizza quello per l'abbattimento. Ma non colgo il motivo profondo del perchè aiuta, cosa cambia?Quello che ho detto io si può qalcosa facilmente, mentre il problema equivalente è più complesso da risolvere :PLuke
Una volta trovata la soluzione magari pensa a come abbattere la sua complessità…;D [non necessario ai fini della risoluzione di questi testcase, ma di altri di dimensione maggiore]
@Luke: guarda il capitolo 7 della guida alle selezioni territoriali, in particolare fino al problema della “dieta di poldo”
Gli stiamo suggerendo 3 metodi diversi: secondo me esplode xD
In ogni caso, se vuoi un approccio generale a questo genere di problemi: http://youtu.be/OQ5jsbhAv_M
si l’ho capito che sono approcci diversi. Forse ne ho trovato uno con la programmazione dinamica che provo ad implementare tra un po’. Però non mi è ancora chiaro com è possibile che si riesca subito a capire se la prima torre va abbattuta o tenuta. Con quello che ho pensato io, son costretto a calcolare tutte le sottosequenze di torri con una cosa che forse sarà quadratica.
si l'ho capito che sono approcci diversi. Forse ne ho trovato uno con la programmazione dinamica che provo ad implementare tra un po'. Però non mi è ancora chiaro com è possibile che si riesca subito a capire se la prima torre va abbattuta o tenuta. Con quello che ho pensato io, son costretto a calcolare tutte le sottosequenze di torri con una cosa che forse sarà quadratica.Non sono a conoscenza di una soluzione lineare (ovvero, come dici te, a capire subito se una torre va eliminata o no), la dinamica è sicuramente quadratica (a meno di non utilizzare dei fenwick per abbassare a NlogN (o almeno credo)).Luke
niente, mi sono accorto che quella che avevo pensato fa ancora acqua! uffa! serve un’idea così elaborata? possibile?
serve un'idea così elaborata? possibile?Serve la programmazione dinamica, e puoi impararla con la guida che ho linkato sopra :)Luke
ma più o meno è così che voglio provare ad implementarlo quasi sin dall’inizio, dopo fallaci tentativi di greedy (come quello di guardare solo la prima torre). Solo che non colgo una valida struttura ricorsiva per poterlo fare. Sono impedito!