Cod sursa(job #134733)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 12 februarie 2008 10:30:55
Problema Subsir 2 Scor 2
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <stdio.h>
long int n, v[5001], best[501], p[501], ok[501], maxim = 10000;

void afis(int i)
{
   if (p[i])  afis(p[i]);
   printf("%d ",i);
}
int main()
{
   freopen("subsir2.in","r",stdin);
   freopen("subsir2.out","w",stdout);
   int i, j;
   long val;

   scanf("%ld",&n);
   for (i = 1; i <= n; i++) scanf("%ld", v + i);
   best[1] = 1; ok[1] = 1;

   for (i = 2; i <= n; i++)
   {
      val = - 2000000;
      for (j = i - 1; j >= 1; j--)
      {
	 if (v[i] > v[j] && (best[j] + 1 > best[i]) && ((val < v[j] || v[i] < val) || val == -2000000))
	 {
	     best[i] = best[j] + 1;
	     if (!p[i] || v[j] < v[p[i]]) p[i] = j;
	     ok[j] = 1;
	 }
         if (v[i] > v[j]) ok[j] = 1;
	 if (val < v[j]) val = v[j];
      }
      if (! best[i]) best[i] = 1;
   }

   for (i = n; i >= 1; i--) if (!ok[i] && best[i] < maxim)
   {
       maxim = best[i];
       val = i;
   }
   printf("%d\n",maxim);
   afis(val);
   return 0;
}