Cod sursa(job #1465951)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 28 iulie 2015 12:46:46
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>

using namespace std;

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

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

int main()
{
    f >> n;
    for (i=1; i<=n; i++)
        f >> v[i];
    for (i=n; i>0; i--)
    {
        min1 = 111111111;
        s = min1;
        for (j=i+1; j<=n; j++)
            if ((v[j]>=v[i]) && (v[j]<min1))
                {
                    min1 = v[j];
                    if (sol[j] <= s)
                    {
                        s = sol[j];
                        p = j;
                    }
            }
        if (min1 == 111111111)
            sol[i] = 1;
        else
        {
            sol[i] = sol[p] + 1;
            bf[i] = p;
        }
    }
    min1 = sol[1];
    p = 1;
    j = v[1];
    for (i=2; i<=n; i++)
        if (v[i] < j)
        {
            j = v[i];
            if (sol[i] <= min1)
            {
                min1 = sol[i];
                p = i;
            }
        }
    g << min1 << "\n" << p << " ";
    while (min1--)
    {
        p = bf[p];
        g << p << " ";
    }
    return 0;
}