La dieta di Poldo fuori tempo limite

Aiuto
1

non capisco come poter ottimizzare il mio codice per farlo rientrare nel tempo massimo, infatti ottengo solo 35/100
condivido il codice:

#include <string>
#include <iostream>
#include <fstream>
#include <cstdio>

using namespace std;

int solve(int N, int P[], int m, int p) {
    if (m == N) {
        return 0;
    } else {
        if (P[m] > p ) {
            return solve(N, P, m+1, p);
        } else {
            return max(solve(N, P, m+1, p), solve(N, P, m+1, P[m])+1);
        }
    }
}

int main() {
    // se preferisci leggere e scrivere da file
    // ti basta decommentare le seguenti due righe:

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int N;
    cin >> N;
    int P[N] = {};

    for (int t = 0; t < N; t++) {
        cin >> P[t];
    }
    cout << solve(N, P, 0, 1000000) << endl;

}
2

Potresti mandare il testo del problema? Non lo conosco. Comunque ad occhio, visto che stai usando una soluzione ricorsiva, devi implementare una cache. É molto semplice farlo, io userei una
map<pair<int, int>, int>, dove nella pair ci salvi m e p, e il risultato della chiamata ricorsiva corrispondente a quella coppia di valori.
Oppure, anche se sará piú complicato ovviamente, potresti provare a convertire il tuo codice per ottennere un vero approccio di Dynamic Programming.

3

Quello della longest increasing subsequence é un problema classico di programmazione dinamica. Puoi utilizzare la soluzione per un prefisso per ricavare quella del prefisso un elemento più lungo? Su internet puoi trovare molte informazioni su questo tipo di problema.

2 Mi Piace
4

grazie, ho cercato un po’ su internet e ho trovato una soluzione molto più veloce