Cod sursa(job #1481512)

Utilizator dnprxDan Pracsiu dnprx Data 4 septembrie 2015 18:01:15
Problema Subsir 2 Scor 73
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <bits/stdc++.h>
#define oo 2000000
using namespace std;

int a[5005], best[5005], n;

void Citire()
{
    int i;
    ifstream fin("subsir2.in");
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    fin.close();
}

void Rezolva()
{
    int i, maxx, lgmin, j, p, x, minim;
    best[n] = 1;
    for (i = n - 1; i >= 1; --i)
    {
        x = a[i];
        /// maxx retine cea mai mica valoare strict mai mare ca x
        maxx = oo;
        lgmin = oo;
        for (j = i + 1; j <= n; ++j)
            if (x <= a[j] && a[j] < maxx && lgmin >= best[j])
            {
                maxx = a[j];
                lgmin = best[j];
            }
        if (lgmin == oo) best[i] = 1;
        else best[i] = 1 + lgmin;
    }

    /// caut cea mai mica valoare best[i], cu a[i]=min{a1,a2,...ai}.
    x = a[1]; p = 1;
    for (i = 2; i <= n; ++i)
        if (best[i] <= best[p] && a[i] < x)
        {
            p = i;
            x = a[i];
        }

    ofstream fout("subsir2.out");
    fout << best[p] << "\n";
    x = a[p];
    fout << p << " ";
    for (int pas = best[p]-1; pas >= 1; pas--)
    {
        /// caut o pozitie in p..n cu best[i]=pas si x<=a[i], a[i]-minim
        minim = oo; j = -1;
        for (i = p + 1; i <= n; i++)
            if (best[i] == pas && x <= a[i] && minim > a[i])
            {
                j = i;
                minim = a[i];
            }
        p = j;
        fout << p << " ";
    }
    fout << "\n";
    fout.close();
}

int main()
{
    Citire();
    Rezolva();
    return 0;
}