Cod sursa(job #1933217)

Utilizator raduzxstefanescu radu raduzx Data 20 martie 2017 16:04:11
Problema Subsir 2 Scor 47
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>

using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
#define nmax 5010
#define inf 2000000000
int n,v[nmax],i,k,x,t[nmax],best[nmax];
bool use[nmax];
void afis(int poz)
{
    if(poz!=0)
    {
        afis(t[poz]);
    g<<poz<<" ";
    }
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i];
        best[i]=0;
    }
    int j;
    for(i=1;i<=n;i++)
    {
       /* if(best[i]==inf)
            best[i]=0;*/
        for(j=i+1;j<=n;j++)
        {
            if(v[j]>v[i])
            {
                if(best[j]<best[i]+1)
                {
                    best[j]=best[i]+1;
                    t[j]=i;
                }
                if(best[j]==best[i]+1)
                {
                    if(v[i]<v[t[j]])
                        t[j]=i;

                }
                use[i]=1;
            }
        }
    }
    int maxim=inf,ok=0;
    for(i=1;i<=n;i++)
    {
        if(use[i]==0)
        {
            if(maxim>best[i])
                {maxim=best[i];k=i;}
            else
                if(maxim==best[i] and v[i]<v[k])
                    k=i;
        }
    }
    g<<maxim+1<<'\n';
    afis(k);
    return 0;
}