Cod sursa(job #2857129)

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

using namespace std;

const int NMAX = 5000;

int n, a[NMAX + 1], t[NMAX + 1], dp[NMAX + 2]; //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]);
    for(int i = 1; i <= n; ++i) {
        dp[i] = 2e9;
        int maxcrt = -2e9;
        for(int j = i - 1; j; --j) {
            if(a[j] > maxcrt && a[j] <= a[i] &&
               (dp[i] > dp[j] + 1 || (dp[i] == dp[j] + 1 && a[t[i]] > a[j]))
              ) {
                dp[i] = dp[j] + 1;
                t[i] = j;
            }
            if(a[j] > maxcrt && a[j] <= a[i]) maxcrt = a[j];
        }
        if(dp[i] == 2e9) dp[i] = 1;
    }

    int poz = n + 1, maxcrt = -2e9, mincrt = 2e9;
    dp[poz] = 2e9;
    for(int i = n; i; --i) {
        if(a[i] > maxcrt && (dp[i] < dp[poz] || (dp[i] == dp[poz] && a[i] < mincrt)))
            poz = i,
            mincrt = a[i];
        maxcrt = max(maxcrt, a[i]);
    }
    printf("%d\n", dp[poz]);
    afisSol(poz);
    return 0;
}