Cod sursa(job #1115975)

Utilizator robertstrecheStreche Robert robertstreche Data 22 februarie 2014 11:40:29
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 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,mi,mii,ma,maa=inf,poz,pozprec,nr;
long long a[lmax],b[lmax],urm[lmax];

int main()
{
    f>>n;

    for (i=1;i<=n;i++)
         f>>a[i];

     b[n]=1;
     urm[n]=n;

     for (i=n-1;i>=1;i--)
     {
         mi=inf;
         mii=inf;
         poz=0;

        for (j=1+i;j<=n;j++)
          if (a[i]<=a[j] && a[j]<mii && b[j]<mi)
           {
               mi=b[j];
               mii=a[j];
               poz=j;

           }
         if (poz)
          {
              b[i]=b[poz]+1;
              urm[i]=poz;
          }
         else
           {
               urm[i]=i;
               b[i]=1;
           }
     }
      mi=inf;

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

      //for (i=1;i<=n;i++)
      //g<<b[i]<<" "<<urm[i]<<'\n';

      g<<ma<<'\n';

     for (i=ma;i>=1;i--)
      {
           g<<poz<<" ";
           poz=urm[poz];
      }

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