Cod sursa(job #2857056)

Utilizator vansJos da pa perete vans Data 24 februarie 2022 20:08:37
Problema Subsir 2 Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 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 = n, maxcrt = 0;
    for(int i = n; i; --i) {
        if(a[i] > maxcrt && dp[i] < dp[poz])
            poz = i;
        maxcrt = max(maxcrt, a[i]);
    }
    printf("%d\n", dp[poz]);
    afisSol(poz);
    return 0;
}