Cod sursa(job #2180452)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 20 martie 2018 21:28:29
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <bits/stdc++.h>
#define N 5000
#define inf 1000001

using namespace std;

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

int n, m, a[N+2], sis[N+2], nxt[N+2];

int main()
{
    int i, j, minv, minsis, pozminsis;
    fin>>n;
    for(i=1; i<=n; i++) fin>>a[i];
    sis[n]=1;
    for(i=n-1; i>=1; i--)
    {
        minv=inf, minsis=inf;
        for(j=i+1; j<=n; j++)
            if(a[j]>=a[i] && a[j]<minv)
                if(sis[j]<=minsis)
                {
                    minsis=sis[j];
                    pozminsis=j;
                    minv=a[j];
                }
        if(minsis==inf) sis[i]=1;
        else sis[i]=sis[pozminsis]+1, nxt[i]=pozminsis;
    }
    for(i=1; i<=n; i++) m=max(m,sis[i]);
    fout<<m<<'\n';
    minv=inf;
    for(i=1; i<=n; i++)
        if(sis[i]==m && a[i]<minv) minv=a[i], pozminsis=i;
    i=pozminsis;
    while(i)
    {
        fout<<i<<' ';
        i=nxt[i];
    }
    return 0;
}