Cod sursa(job #2019092)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 6 septembrie 2017 22:16:39
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
using namespace std;
const int NMAX = 5005;
int v[NMAX];
int a[NMAX];
int nextt[NMAX];

int main()
{
    int n;
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    scanf("%d", &n);
    for(int i = 1;i <= n; ++i) {
        scanf("%d", &v[i]);
    }
    for(int i = n;i > 0; --i) {
        int minim = 0x7fffffff;
        for(int j = i + 1;j <= n; ++j) {
            if(v[i] <= v[j] && v[j] < minim) {
                minim = v[j];
                if(a[i] >= a[j] || a[i] == 0) {
                    a[i] = a[j];
                    nextt[i] = j;
                }
            }
        }
        ++a[i];
    }
    int last = 1, minim = v[1];
    for(int i = 2;i <= n; ++i) {
        if(v[i] < minim) {
            minim = v[i];
            if(a[i] <= a[last]) {
                last = i;
            }
        }
    }
    printf("%d\n", a[last]);
    for(int i = last;i > 0;i = nextt[i]) {
        printf("%d ", i);
    }
    printf("\n");
    return 0;
}