Cod sursa(job #1745289)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 21 august 2016 16:38:33
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 5005,
           INF = 1e9;

int v[NMAX],
    f[NMAX],
    l[NMAX];

int main(void) {
    freopen("subsir2.in",  "r", stdin);
    freopen("subsir2.out", "w", stdout);
    int n, t, mn, ant;

    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
        scanf("%d",&v[i]);

    for(int i=n; i>=1; --i) {
        mn   = INF;
        t    = NULL;

        for(int j=i+1; j<=n; ++j) {
            if(mn>v[j] && v[i]<=v[j]) {
                if(l[i]==0 || l[j]<=l[i]) {
                    l[i] = l[j];
                    f[i] = j;
                }

                mn = v[j];
                l[i] ++;
            }
        }
    }

    ant = 1;
    mn  = v[1];

    for(int i=2; i<=n; ++i) {
        if(v[i] < mn) {
            if(l[i] >= l[ant])
                ant = i;
            mn  = v[i];
        }
    }

    printf("%d\n",l[ant]+1);
    for(int i=ant; i; i=f[i])
        printf("%d ",i);
    printf("\n");

    fclose(stdin);
    fclose(stdout);
    return 0;
}