# Problema discesa massima **URL:** \ **Category:** Aiuto\ **Created:** [29 Agosto 2019, 1:24pm UTC](https://forum.olinfo.it/t/problema-discesa-massima/5814 "2019-08-29T13:24:06Z")\ **Posts on this page:** 14\ **Page:** 1
**Author:** ![Ico456bart](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ico456bart/32/641_2.png) [@Ico456bart](https://forum.olinfo.it/u/Ico456bart)\ **Post date:** [29 Agosto 2019, 1:24pm UTC](https://forum.olinfo.it/t/problema-discesa-massima/5814/1 "2019-08-29T13:24:06Z")
Non capisco come gestire i casi in cui nella stessa riga ci sono due numeri uguali sotto al numero maggiore della riga precedente… ```auto #include #include int main() { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); int A, i, N, max, sum=0, p; scanf("%i", &A); assert(A>=1 && A<=10); for(i=1; i<=A; i++) { max=-1; for(int k=0; k=1); if(i==1) { max=N; p=k; break; } else { if(N>max && (k==p || k==(p+1))) { max=N; p=k; } } } sum=sum+max; } printf("%i", sum); return 0; } ``` ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [29 Agosto 2019, 1:51pm UTC](https://forum.olinfo.it/t/problema-discesa-massima/5814/2 "2019-08-29T13:51:24Z")
In realtà il problema è un altro, stai usando un approccio greedy incorretto, non è infatti sufficiente scendere scegliendo sempre il nodo massimo tra i 2 figli disponibili. Un esempio è ```auto 3 1 1 2 10 1 1 ``` ---
**Author:** ![Ico456bart](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ico456bart/32/641_2.png) [@Ico456bart](https://forum.olinfo.it/u/Ico456bart)\ **Post date:** [29 Agosto 2019, 1:56pm UTC](https://forum.olinfo.it/t/problema-discesa-massima/5814/3 "2019-08-29T13:56:50Z")
Ho provato anche con questo ma sempre 20/100 ```auto #include #include int main() { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); int A, i, N, max=-1, sum=0; scanf("%i", &A); assert(A>=1 && A<=10); for(i=1; i<=A; i++) { max=-1; for(int k=0; kmax) max=N; } sum=sum+max; } printf("%i", sum); return 0; } ``` ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [29 Agosto 2019, 1:59pm UTC](https://forum.olinfo.it/t/problema-discesa-massima/5814/4 "2019-08-29T13:59:30Z")
È sbagliato perché scegli i valori massimi di ogni livello senza controllare se siano collegati o meno, infatti sbagli anche il testcase che ti ho dato prima. Questo esercizio è classico nella programmazione dinamica. ---
**Author:** ![Ico456bart](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ico456bart/32/641_2.png) [@Ico456bart](https://forum.olinfo.it/u/Ico456bart)\ **Post date:** [29 Agosto 2019, 2:04pm UTC](https://forum.olinfo.it/t/problema-discesa-massima/5814/5 "2019-08-29T14:04:24Z")
Può darsi che non ho capito bene il problema allora. ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [29 Agosto 2019, 2:12pm UTC](https://forum.olinfo.it/t/problema-discesa-massima/5814/6 "2019-08-29T14:12:42Z")
Partendo dalla radice devi scegliere fino ad una foglia, per farlo attraversi A nodi sommando i valori dei nodi su cui sei passato, tra i vari percorsi devi trovare la somma del percorso con somma massima. ---
**Author:** ![Ico456bart](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ico456bart/32/641_2.png) [@Ico456bart](https://forum.olinfo.it/u/Ico456bart)\ **Post date:** [29 Agosto 2019, 2:44pm UTC](https://forum.olinfo.it/t/problema-discesa-massima/5814/7 "2019-08-29T14:44:34Z")
Quindi in pratica devi fare tutti i percorsi e infine dire il maggiore? ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [29 Agosto 2019, 2:53pm UTC](https://forum.olinfo.it/t/problema-discesa-massima/5814/8 "2019-08-29T14:53:24Z")
Tu devi dire solo la somma massima, il modo in cui la trovi varia in base al ragionamento che fai, un modo, come hai detto tu, un modo può essere quello di calcolare tutte le somme e stampare la massima. Utilizzando la programmazione dinamica si può evitare di calcolare esplicitamente ogni percorso. Provo ad aiutarti: Come ti ho fatto notare prima: da un nodo non è possibile capire se conviene maggiormente muoversi verso sinistra o verso destra sapendo solo solo i valori dei nodi figli, ma se sapessimo quale dei 2 nodi offre poi un percorso con somma massima allora la richiesta diventa banale. ---
**Author:** ![Ico456bart](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ico456bart/32/641_2.png) [@Ico456bart](https://forum.olinfo.it/u/Ico456bart)\ **Post date:** [29 Agosto 2019, 2:56pm UTC](https://forum.olinfo.it/t/problema-discesa-massima/5814/9 "2019-08-29T14:56:54Z")
Ok forse ho capito. Adesso ci lavoro su. Grazie comunque per la pazienza 😅 ---
**Author:** ![Ico456bart](https://forum.olinfo.it/user_avatar/forum.olinfo.it/ico456bart/32/641_2.png) [@Ico456bart](https://forum.olinfo.it/u/Ico456bart)\ **Post date:** [29 Agosto 2019, 4:00pm UTC](https://forum.olinfo.it/t/problema-discesa-massima/5814/10 "2019-08-29T16:00:54Z")
Mi sa che per risolverlo servono array bidimensionali, vero? Perché in questo caso non saprei come utilizzarli. ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [29 Agosto 2019, 4:05pm UTC](https://forum.olinfo.it/t/problema-discesa-massima/5814/11 "2019-08-29T16:05:48Z")
Allora ti consiglio di svolgere prima gli esercizi con il tag implementation, e poi riprendere questo esercizio. ---
**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\ **Post date:** [29 Agosto 2019, 6:11pm UTC](https://forum.olinfo.it/t/problema-discesa-massima/5814/12 "2019-08-29T18:11:37Z")
Puoi anche partire dal basso, specialmente se preferisci gli approcci greedy. ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [29 Agosto 2019, 7:51pm UTC](https://forum.olinfo.it/t/problema-discesa-massima/5814/13 "2019-08-29T19:51:12Z")
Pur partendo dal basso l’approccio è comunque la programmazione dinamica, il fatto che sia bottom up non lo rende greedy. Infatti se così fosse un qualsiasi problema dp risolto in bottom up risulterebbe greedy. ---
**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\ **Post date:** [29 Agosto 2019, 8:53pm UTC](https://forum.olinfo.it/t/problema-discesa-massima/5814/14 "2019-08-29T20:53:41Z")
Non ho molta dimestichezza con la teoria, volevo dire che, in questo caso, me la cavavo con una procedura iterativa che in ogni nodo trova immediatamente il meglio che si può fare partendo da lì.