Cod sursa(job #1115931)

Utilizator robertstrecheStreche Robert robertstreche Data 22 februarie 2014 10:44:01
Problema Subsir 2 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#define lmax 5001
#define inf 10000000

using namespace std;

ifstream f("subsir2.in");
ofstream g("subsir2.out");

long long i,j,n,ma=inf,maa,poz,pozprec,nr;
long long a[lmax],b[lmax];

int main()
{
    f>>n;

    for (i=1;i<=n;i++)
     {
         f>>a[i];
         b[i]=inf;
     }

     b[n]=1;

     for (i=n-1;i>=1;i--)
      for (j=1+i;j<=n;j++)
        if (a[i]<=a[j] && b[i]>b[j]+1 && (b[i]==inf || b[j]!=1))
         b[i]=b[j]+1;

     for (i=1;i<=n;i++)
       if (a[i]<ma)
        {
            ma=a[i];
            maa=b[i];
            poz=i;
        }



      g<<maa<<'\n';

     pozprec=poz-1;

     for (i=maa;i>=1;i--)
      {
          nr=inf;

          for (j=pozprec+1;j<=n;j++)
            if (b[j]==i && a[j]<nr)
             {
               poz=j;
               nr=a[j];
             }

           g<<poz<<" ";
           pozprec=poz;
        }

    f.close();
    g.close();
}