Cod sursa(job #1745278)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 21 august 2016 16:24:35
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 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=n; j>i; --j) {
            if(mn>v[j] && v[i]<=v[j]) {
                if(l[i]==0 || l[j]<=l[i]) {
                    l[i] = l[j] + 1;
                    f[i] = j;
                }

                mn = v[j];
            }
        }
    }

    ant = n;
    mn  = v[n];

    for(int i=n-1; i>=1; --i)
        if(l[i] > l[ant] && v[i] < mn)
            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;
}