Cerinţa

Se dă un șir cu n elemente, numere naturale. Determinați un cel mai lung subșir crescător al șirului.

Date de intrare

Fişierul de intrare sclm.in conţine pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spaţii, reprezentând elementele șirului.

Date de ieşire

Fişierul de ieşire sclm.out va conţine pe prima linie numărul L, reprezentând lungimea maximă a unui subșir crescător. A doua linie va conține L numere cu valori între 1 și n, ordonate crescător, reprezentând indicii elementelor din șirul dat care dau subșirul crescător de lungime maximă.

Restricţii şi precizări

1 ≤ n ≤ 1000
numerele de pe a doua linie a fişierului de intrare vor fi cel mult egali cu 1.000.000
orice șir de indici care duce la subșir crescător de lungime maximă este corect

Exemplu

sclm.in

10
5 10 7 4 5 8 9 8 10 2

sclm.out

5
1 3 6 7 9

Explicație

Elementele șirului care corespund acestor indici sunt: 5 7 8 9 10.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema SCLM:

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
using namespace std;
#define NN 1005

ifstream fin("sclm.in");
ofstream fout("sclm.out");

int n, a[NN], L[NN], Next[NN];


int main(){
    assert(fin >> n );
    for(int i=1 ; i<=n ; ++i)
        assert(fin >> a[i]);
    L[n] = 1;
    Next[n] = -1;
    for(int i=n-1 ; i>0 ; i--)
    {
        L[i] = 1, Next[i] = -1;
        for(int j=i+1 ; j<=n; ++j)
            if(a[i]<=a[j] && L[i]<L[j]+1)
                L[i] = L[j] + 1, Next[i] = j;
    }
    int pmax = 1;
    for(int i=1 ; i<=n ; ++i)
        if(L[pmax] < L[i])
            pmax = i;
    fout << L[pmax] << endl;
    for(int i=pmax ; i!=-1 ; i = Next[i])
        fout << i << " ";
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #396 SCLM

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #396 SCLM de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #396 SCLM