La dieta di Poldo

#1

Salve a tutti,
Sto provando a risolvere ‘Poldo’ da un po’, sono convinto che la mia idea (DP ricorsiva) sia corretta, ma forse sbaglio qualcosa nel codice (ottengo 0pt).
Qui c’è il mio codice: ‘https://pastebin.com/Uwkrbj6p’
Grazie in anticipo :slight_smile:

#2

Mi sembra che non funzioni perchè la memoizzazione dipende da due variabili una è il panino sotto analisi l’altra dipende da come sei arrivato ad analizzare quel panino, ovvero dall’ultimo panino mangiato da Poldo in precedenza. Inoltre in questo caso un array per memo può occupare troppa memoria.

#3

La versione che riporto sotto funzionerebbe pure se non sforasse la memoria negli ultimi due test case: Fa comunque 85/100
D’altra parte:

  1. valore massimo del peso di un panino 10000g

  2. numero massimo di panini sempre 10000

  3. il valore massimo da memoizzare sempre 10000 quindi uno short int basta

ma anche così la memoria solo per memo (nel caso peggiore) è 10000x10000x2=200MB e guarda caso la memoria a disposizione era solo di 64MB. Sarà solo un caso?

#include <stdio.h>
#include <vector>
using namespace std;
#define MAXN 10000
#define max(a, b) ((a) > (b) ? (a) : (b))

int N;
int P[MAXN];
vector<vector<short int>>	memo; //[MAXN+2][MAXN];

int dp(int u, int prec) {
	int caso;
	caso=prec>P[u]?1:0;
    if(u >= N) return 0;
    if(memo[u][prec] != -1) 
		return memo[u][prec];
    int yes = 0;
	int no = dp(u+1, prec);
    if(caso) 
		yes = dp(u+1, P[u])+1;
    memo[u][prec] = max(yes, no);
    return max(yes, no);
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    scanf("%d", &N);
	memo.resize(N);
   
	int maxpeso=0;
    for(int i = 0; i < N; i++){
		scanf("%d", P+i);
		if(maxpeso<P[i])
			maxpeso=P[i];
	}
	for(int i=0;i<N;i++)
		memo[i].resize(maxpeso+2);
	 for(int i = 0; i < N; i++) {
		for(int j = 0; j <= maxpeso+1; j++)
			memo[i][j]= -1;
	}
    int ris=dp(0, maxpeso+1);
    printf("%d",ris); 
    return 0;
}
#4 
int dp(int u, int prec) {
if(u >= N) return 0;
if(memo[u][prec] != -1) return memo[u][prec];
int yes = 0, no = dp(u+1, prec);
if(P[u] < prec) yes = dp(u+1, P[u])+1;
return memo[u][prec] = max(yes, no);
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%d", &N);
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++) memo[i][j] = -1;
    for(int i = 0; i < N; i++) scanf("%d", P+i);
    dp(0, MAXN);
    int mass = -1;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(memo[i][j] > mass) mass = memo[i][j];
        }
    }
    printf("%d", mass);
    return 0;
}

Così tutti gli output sono comunque errati…

#5

Ma hai messo a commento due righe di codice fondamentali:

ma in questa piattaforma l’I/O non è da console, i dati vanno letti dal file “input.txt” e il risultato va scritto sul file “output.txt” lo richiede espressamente il testo (ed quasi sempre così).
Se vuoi provare il tuo codice ti devi creare un file input.txt ed andare a vedere cosa il programma scrive sul file output.txt che genera.

#6

:roll_eyes: Mi sembrava scontato dire che le due righe sono commentate perché in locale leggo direttamente da console ed ovviamente levo i commenti quando sottopongo… In ogni caso gli output sono errati (non solo sulla piattaforma ma anche in locale)

#7

Non so che dire ho appena copiato dal post il mio codice, ho fatto una nuova sottomissione e ho di nuovo fatto 85/100.

Ho provato l’ultimo che hai postato e non va neanche a me, ma rispetto al mio ci sono differenze fondamentali
ad esempio qui:

non è N nel secondo ciclo for ma il massimo peso dei panini presenti in input!
N va bene come massimo del primo indice ma non del secondo.
Si possono avere anche solo 3 panini ma uno di essi pesa 10000g!!
Il fatto che sia il numero dei panini che il loro peso possano entrambi valere 10000 induce in errore.
Inoltre perchè andare a scandire memo quando dp restituisce la soluzione?
L’ultimo programma che hai postato non è completo (mancano istruzioni in testa) e non vedo il dimensionamento di memo che deve essere fatto a run-time altrimenti si eccede la memoria anche con 4 panini.
Saluti