Cod sursa(job #1465934)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 28 iulie 2015 12:19:09
Problema Subsir 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#define INF 10000001

using namespace std;

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

int n, i, j;
int v[5005], sol[5005], bf[5005];
int minim, s, p;

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

    for (i = n; i >= 1; i--)
    {
        minim = s = INF;
        for (j = i+1; j <= n; j++)
            if (v[j] >= v[i] && v[j] < minim)
            {
                minim = v[j];
                if (sol[j] <= s)
                    s = sol[j], p = j;
            }
        if (minim == INF)
            sol[i] = 1;
        else
            sol[i] = sol[p]+1, bf[i] = p;
    }
    minim = s = INF;
    for (i = 1; i <= n; i++)
        if (v[i] <= minim)
        {
            minim = v[i];
            if (sol[i] <= s)
                s = sol[i], p = i;
        }

    g << s << "\n" << p << " ";
    s--;
    while (s > 0)
    {
        p = bf[p];
        g << p << " ";
        s--;
    }
    return 0;
}