Cod sursa(job #2020914)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 12 septembrie 2017 09:48:25
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>

using namespace std;

ifstream f("subsir2.in");
ofstream g("subsir2.out");

const int nmax = 5005;
int i, j, n, a[nmax], b[nmax], c[nmax], min1, min2;

int main() {
    f >> n;
    for (i = 1; i <= n; i++)
        f >> a[i];

    a[0] = b[0] = 1e9;
    for (i = n; i >= 1; i--) {
        min1 = 1e9;
        min2 = 0;
        for (j = i+1; j <= n; j++)
            if (a[i] <= a[j] && min1 > a[j]) {
                min1 = a[j];
                if (b[j] <= b[min2])
                    min2 = j;
            }

        if (min1 == 1e9)
            c[i] = n+1, b[i] = 1;
        else c[i] = min2, b[i] = min1+1;

    }

    min1 = a[1];
    min2 = 1;
    for (i = 2; i <= n; i++)
        if (min1 > a[i]) {
            min1 = a[i];
            if (b[i] <= b[min2])
                min2 = i;
        }
    i = min2;
    min2 = b[min2];
    g << min2 << '\n';
    while (min2) {
        g << i << ' ';
        i = c[i];
        min2--;
    }

}