Ciao a tutti! Ho provato ripetutamente a risolvere ‘La dieta di Poldo’, completamente a mio modo pur sapendo che ne esistono tanti altri. Non capisco perchè ricevo solo 5/100, lascio il codice qui:
#include
#include
#include
using namespace std;
int main() {
ios::sync_with_stdio(false);
ifstream cin("input.txt");
ofstream cout("output.txt");
int N,mangiati=1,massimo=1,i=0;
cin >> N;
vector<int> V(N);
for(int i = 0; i < N; i++) {
cin >> V[i];
}
i = 0;
for(int i=0;i<N-1;i++){
if (V[i]>V[i+1]) mangiati = mangiati + 1;
else if (mangiati > massimo){
massimo = mangiati; mangiati = 1;
}
else mangiati = 1;
}
if (mangiati > massimo) massimo = mangiati;
cout << massimo;
return 0;
}
Come posso fare?? 
Per risolvere questo problema ho usato la dp, tenendo in considerazione le migliori combinazioni possibili. Il tuo codice invece scarta molte altre combinazioni che portano alla soluzione. Considera questo input:
5
5 6 2 4 3
Il tuo codice da come risultato 2, combinando il piatto di peso 6 con quello di peso 2, quando la migliore combinazione è scegliere il secondo piatto (di peso 6) il quarto piatto (di peso 4) e l’ultimo piatto (di peso 3)
Inizialmente non avevo letto e capito che si potesse scartare uno o più panini. Detto questo ho sentito parlare molto di dp, senza capire come poterla davvero applicare al problema, sai darmi un indizio? Grazie! =)
Per risolvere il problema, innanzitutto ho cambiato punto di vista: con la dp quello che fai è dividere il problema in sottoproblemi, cercando la soluzione migliore per ognuno e unendo quelle che trovi per ottenere la soluzione finale.
Riesci a trovare un modo per dividerlo in sottoproblemi?
Hint:
Immagina di avere un solo panino, come ti comporteresti? E se ne aggiungessi uno ad ogni passo, quale sarebbe la soluzione ottima ad ogni situazione?
1 Mi Piace
