Cod sursa(job #2150523)

Utilizator ivddabDabelea Ioana-Viviana ivddab Data 3 martie 2018 16:55:25
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#define MX 10000005
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int n,i,j,min1,k,p,nr;
int v[5001],l[5001],fol[5001],pr[5001],poz[5001],pre[5001];
int main()
{
    f>>n;
    for(i=1;i<=n;i++) f>>v[i];
    for(i=n;i>=1;i--){
        min1=MX;
       // max1=n+1;
        for(j=i+1;j<=n;j++){
            if(v[j]>=v[i]&&v[j]<min1){
                min1=v[j];
                fol[j]=1;
                if(l[i]>=l[j]+1||l[i]==0){
                    l[i]=l[j]+1; pre[i]=j;
                }
            }
        }
        if(pre[i]==0){ l[i]=1; pre[i]=n+1; }
    }
    min1=MX;
    k=n+1;
    for(i=1;i<=n;i++)
      if(fol[i]==0){
        nr=0; p=i;
        while(p<=n){
            poz[++nr]=p;
            p=pre[p];
        }
        if(nr<k){
            k=nr; min1=v[i];
            for(j=1;j<=k;j++) pr[j]=poz[j];
        }
        if(nr==k&&v[i]<min1){
            k=nr; min1=v[i];
            for(j=1;j<=k;j++) pr[j]=poz[j];
        }
      }
    g<<k<<'\n';
    for(i=1;i<=k;i++) g<<pr[i]<<' ';
    return 0;
}