Cod sursa(job #2857052)

Utilizator vansJos da pa perete vans Data 24 februarie 2022 20:05:10
Problema Subsir 2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <algorithm>
#include <iostream>

using namespace std;

const int NMAX = 5000;

int n, a[NMAX + 1], t[NMAX + 1], dp[NMAX + 1]; //dp[i] = lungimea celui mai scurt scm

inline void afisSol(const int X) {
    if(t[X]) afisSol(t[X]);
    printf("%d ", X);
}

int main()
{
    freopen("subsir2.in", "r", stdin);
    //freopen("subsir2.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int ans = 1;
    for(int i = 1; i <= n; ++i) {
        dp[i] = 1;
        for(int j = i - 1; j; --j) {
            if(a[j] <= a[i]) {
                dp[i] = dp[j] + 1;
                t[i] = j;
                break;
            }
        }
    }
    int poz = distance(dp, max_element(dp + 1, dp + n + 1));
    printf("%d\n", dp[poz]);
    afisSol(poz);
    return 0;
}