Cod sursa(job #2014344)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 23 august 2017 14:41:50
Problema Subsir 2 Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>
#define nmax 5005
using namespace std;
fstream f1("subsir2.in", ios::in);
fstream f2("subsir2.out", ios::out);
int n, a[nmax], t[nmax], nu[nmax];
long int v[nmax];
///a[i]= lungimea celui mai scurt subsir cresc maximal care incepe de pe poz i
///t[i]= indicele urmatorului el in cel mai scurt subsor maximal care incepe de pe poz i
void citire()
{
   int i, j;
   long int  mini, ind;
   f1>>n;
   for(i=1; i<=n; i++) f1>>v[i];

   a[n]=1;
   t[n]=0;
   for(i=n-1; i>=1; i--)
       {
            mini=0; ///=min (v[k], j>k>i)  a.i v[k]>=v[i]
            ind=0;
            for(j=i+1; j<=n; j++)
                if((v[i]<=v[j])&&((!mini)||(v[j]<mini)))
                {
                    mini=v[j];
                    if((!ind)||((a[ind]> a[j])||((a[ind]==a[j])&&(v[ind]> v[j])))) ind=j;
                }
           a[i]=a[ind]+1;
           t[i]=ind;
       }

}
void afisare()
{
   int i, ind=0;
   long int  mini;

   mini=v[1];
   for(i=2; i<=n; i++)
       if(mini> v[i]) mini=v[i];
       else nu[i]=1; ///subsirul poate fi extins la stanga

   ///cauti a[i] minim nu[i]=0 si v[i] minim
   i=1;
   mini=0;
   while((i<=n)&&(nu[i])) i++;
   if(i<=n) {mini=a[i];ind=i;}
   while(i<=n)
   {
       if((!nu[i])&&((a[i]< mini)||((a[i]==mini)&&(v[i]< v[ind]))||((a[i]==mini)&&(v[i]==v[ind])&&(t[v[i]]< t[v[ind]])))) {mini=a[i];ind=i;}
       i++;
   }

   f2<<mini<<"\n";
   while(ind)
   {
       f2<<ind<<' ';
       ind=t[ind];
   }
}
int main()
{
    citire();
    afisare();
    return 0;
}