Problema discesa massima


#1

Non capisco come gestire i casi in cui nella stessa riga ci sono due numeri uguali sotto al numero maggiore della riga precedente…

#include <stdio.h>
#include <assert.h>

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<i; k++)
		{
			scanf("%i", &N);
			assert(N<=100 && N>=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;
}

#2

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 è

3
1
1 2 
10 1 1 

#3

Ho provato anche con questo ma sempre 20/100

#include <stdio.h>
#include <assert.h>

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; k<i; k++)
		{
			scanf("%i", &N);
			assert(N<=100);
			if(N>max)
				max=N;
		}
		sum=sum+max;
	}
	printf("%i", sum);
	return 0;
}

#4

È 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.


#5

Può darsi che non ho capito bene il problema allora.


#6

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.


#7

Quindi in pratica devi fare tutti i percorsi e infine dire il maggiore?


#8

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.


#9

Ok forse ho capito. Adesso ci lavoro su. Grazie comunque per la pazienza :sweat_smile:


#10

Mi sa che per risolverlo servono array bidimensionali, vero? Perché in questo caso non saprei come utilizzarli.


#11

Allora ti consiglio di svolgere prima gli esercizi con il tag implementation, e poi riprendere questo esercizio.


#12

Puoi anche partire dal basso, specialmente se preferisci gli approcci greedy.


#13

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.


#14

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ì.