Cod sursa(job #1817132)

Utilizator Bodo171Bogdan Pop Bodo171 Data 27 noiembrie 2016 13:28:09
Problema Subsir 2 Scor 73
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
int nxt[5005],best[5005],maxim,minim,mn,minbest,v[5005],i,j,n,poz,minpoz,mx,ind[5005];
bool del[5005];
bool comp(int unu,int doi)
{
    if(v[unu]==v[doi]) return unu<doi;
    return v[unu]<v[doi];
}
int main()
{
    ifstream f("subsir2.in");
    ofstream g("subsir2.out");
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i];
    }
    for(i=1;i<=n;i++)
        best[i]=(1<<30);
    maxim=-(1<<30);
    minim=(1<<30);
    for(i=n;i>=1;i--)
    {
        if(v[i]>maxim)
        {
            maxim=v[i];
            best[i]=1;
        }
        mx=-(1<<30);
        for(j=i-1;j>=1;j--)
        {
            if(v[j]>mx&&v[j]<=v[i])
            {
                mx=v[j];
                if(best[i]+1<best[j])
                {
                    best[j]=best[i]+1;
                }
            }
        }
    }
    minbest=(1<<30);minpoz=(1<<30);
    for(i=1;i<=n;i++)
    {
      if(v[i]<minim)
        {
            minim=v[i];
            if(best[i]<minbest)
        {
            minbest=best[i];
        }
        }
    }
    g<<minbest<<'\n';
    for(i=1;i<=n;i++)
    {
        ind[i]=i;
    }
    sort(ind+1,ind+n+1,comp);
    for(i=1;i<=n;i++)
    {
        if(best[ind[i]]==minbest&&del[i]==0)
        {
            minbest--;
            g<<ind[i]<<' ';
            for(j=i+1;j<=n;j++)
                if(ind[j]<ind[i])
                 del[j]=1;
        }
    }
    return 0;
}