Cod sursa(job #1041119)

Utilizator radu2004GOLD radu radu2004 Data 25 noiembrie 2013 15:40:25
Problema Subsir 2 Scor 2
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <stdio.h>

using namespace std;
FILE *f,*g;
int i,n,j,max1,v[5003],t[5003],a[5003],l[5003],urm[5003],poz,nr,p1,p2;

int main()
{f=fopen ("subsir2.in","r");
 g=fopen ("subsir2.out","w");
 fscanf (f,"%d",&n);
 for (i=1;i<=n;i++) fscanf (f,"%d",&a[n-i+1]);
 for (i=1;i<=n;i++)
 {   max1=10000000;
     for (j=i-1;j>=1;j--)
     {   if (a[j]<max1 && a[j]>=a[i]) max1=a[j];
         if (a[j]>=a[i] && ((l[j]+1<l[i] || l[i]==0) || (l[j]+1==l[i] && a[i]<a[urm[j]])) && (a[j]<=max1))
         {
             l[i]=l[j]+1;
             v[i]=j;
             urm[j]=i;
             t[j]=0;

             t[i]=1;

         }



     }
     if (l[i]==0)
       {
        l[i]=1;
        v[i]=i;

        t[i]=1;}
 }
 max1=1000000000;
 for (i=n;i>=1;i--)
 {
     if (t[i]==1 && l[i]<max1)
     {
         max1=l[i];
         poz=i;
     }
     else if (l[i]==max1 && a[i]<a[poz] && t[i]==1)
        {
         max1=l[i];
         poz=i;
        }
        else if (l[i]==max1 && a[i]==a[poz])
        {
            p1=i;p2=poz;
            while (a[p1]==a[p2] && v[p1]==p1)

            {
                p1=v[p1];
                p2=v[p2];
            }
            if (a[p1]<a[p2])
            {
                max1=l[i];
                poz=i;
            }

        }

 }
 while (v[poz]!=poz)
 {
     t[++nr]=poz;
     poz=v[poz];
 }
 t[++nr]=poz;
 fprintf (g,"%d\n",max1);
 for (i=1;i<=nr;i++)
    fprintf (g,"%d ",n-t[i]+1);

    return 0;
}