Cod sursa(job #2943926)

Utilizator rapidu36Victor Manz rapidu36 Data 21 noiembrie 2022 20:02:50
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <bitset>

using namespace std;

const int N = 5000;
const int INF = 1 << 20;

int lung[N], v[N], urm[N], n;

int main()
{
    ifstream in("subsir2.in");
    ofstream out("subsir2.out");
    in >> n;
    for (int i = 0; i < n; i++)
    {
        in >> v[i];
    }
    bitset<N> prim;
    prim.set();
    lung[n - 1] = 1;
    urm[n - 1] = -1;
    for (int i = n - 2; i >= 0; i--)
    {
        lung[i] = n + 1;
        int minim = INF;
        for (int j = i + 1; j < n; j++)
        {
            if (v[i] <= v[j])
            {
                if (v[j] < minim)///pot pune v[i] la inc. sirului optim din j
                {
                    minim = v[j];
                    if (lung[j] <= lung[i])
                    {
                        lung[i] = lung[j];
                        urm[i] = j;
                    }
                }
                prim[j] = 0;
            }
        }
        if (lung[i] == n + 1)
        {
            lung[i] = 1;
            urm[i] = -1;
        }
        else
        {
            lung[i]++;
        }
    }
    int p = 0, lmin = n + 1;
    for (int i = 0; i < n; i++)
    {
        //out << i << ": " << lung[i] << " " << prim[i] << " " << urm[i] << "\n";
        if (prim[i] && (lung[i] < lmin || (lung[i] == lmin && v[i] < v[p])))
        {
            lmin = lung[i];
            p = i;
        }
    }
    out << lmin << "\n";
    while (p != -1)
    {
        out << p + 1 << " ";
        p = urm[p];
    }
    in.close();
    out.close();
    return 0;
}