Cod sursa(job #2669596)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 7 noiembrie 2020 12:12:27
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("subsir2.in");
ofstream fout ("subsir2.out");

const int INF=1000001;
int v[5001], l[5001];

int main()
{
    int n, i, j, mn, rez, x, poz, mn1;
    fin>>n;
    for(i=1; i<=n; i++)
    {
        fin>>v[i];
    }
    for(i=n; i>=1; i--)
    {
        mn=INF;
        l[i]=INF;
        for(j=i+1; j<=n; j++)
        {
            if(v[i]<=v[j] && v[j]<mn)
            {
                l[i]=min(l[i], l[j]+1);
                mn=v[j];
            }
        }
        if(l[i]==INF) l[i]=1;
    }

    rez=INF;
    mn=INF;
    for(i=1; i<=n; i++)
    {
        if(v[i]<mn)
        {
            mn=v[i];
            rez=min(rez, l[i]);
        }
    }
    fout<<rez<<"\n";

    x=-INF;
    poz=0;
    while(rez)
    {
        mn1=INF;
        for(i=poz+1; i<=n; i++)
        {
            if(v[i]>=x && v[i]<mn1)
            {
                if(l[i]==rez) poz=i;
                mn1=v[i];
            }
        }
        fout<<poz<<' ';
        x=v[poz];
        rez--;
    }
}