Aiuto per La dieta di Poldo (poldo)

Aiuto
1

Ciao a tutti, ho bisogno di aiuto per risolvere il problema La dieta di Poldo.

Ciao a tutti, non riesco a passare il subsack 3, 4 e 5, qualcuno mi potrebbe dare una mano?
Ho usato un metodo simile a quello della soluzione O(n log n) del Longest increasing subsequence ma non ho capito dove ho sbagliato.

Ecco il mio codice:

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    ifstream cin("input.txt");
    ofstream cout("output.txt");

    int N;
    cin>>N;
    vector<int> P(N);

    for (int i=0; i<N; i++) cin>>P[i];

    vector<int> ans{P[0]};
    for (int i=1; i<N; i++){
        if (ans.back() > P[i]) ans.push_back(P[i]);
        else{
            //ricerca binaria
            int it = ans.size()-1;
            for (int speed = ans.size() / 2; speed > 0; speed /= 2)
                while (it - speed >= 0 && P[i] > ans[it - speed]) it -= speed;

            ans[it] = P[i];
        }
    }

    cout<<ans.size()<<endl;

    return 0;
}

Grazie mille in anticipo!

2 
// Function that returns the length
// of the longest decreasing subsequence
int lds(vector<int>&arr, int n)
{
    //int lds[n];
    vector<int>lds(n);
    int i, j, max = 0;

    // Initialize LDS with 1 for all index
    // The minimum LDS starting with any
    // element is always 1
    for (i = 0; i < n; i++)
        lds[i] = 1;

    // Compute LDS from every index
    // in bottom up manner
    for (i = 1; i < n; i++)
        for (j = 0; j < i; j++)
            if (arr[i] < arr[j] && lds[i] < lds[j] + 1)
                lds[i] = lds[j] + 1;

    // Select the maximum 
    // of all the LDS values
    for (i = 0; i < n; i++)
        if (max < lds[i])
            max = lds[i];

    // returns the length of the LDS
    return max;
}

Ho provato questo algoritmo per il calcolo della “longest decreasing subsequence”
e funziona, non usa però quella parte che hai chiamato ricerca binaria e forse è questa che è da rivedere.

1 Mi Piace
3 
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ifstream cin("input.txt");
    ofstream cout("output.txt");

    int N;
    cin >> N;
    vector<int> P(N);

    for (int i = 0; i < N; i++) cin >> P[i];

    vector<int> ans{ P[0] };
    for (int i = 1; i < N; i++) {
        if (ans.back() > P[i]) ans.push_back(P[i]);
        else {
            //ricerca binaria
            int it = lower_bound(ans.begin(), ans.end(), P[i], greater<int>()) - ans.begin();
            /*
            int it = ans.size() - 1;
            for (int speed = ans.size() / 2; speed > 0; speed /= 2)
                while (it - speed >= 0 && P[i] > ans[it - speed]) it -= speed;
            */
            ans[it] = P[i];
        }
    }

    cout << ans.size() << endl;

    return 0;
}

Funziona anche la tua soluzione ma con la ricerca binaria che usa lower_bound().

1 Mi Piace
4

grazie mille