Cod sursa(job #134760)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 12 februarie 2008 11:25:01
Problema Subsir 2 Scor 49
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
long int n, v[5001], best[5001], p[5001], ok[5001], maxim, k;

void afis(int i)
{
   maxim++;
   if (p[i] > 0)  afis(p[i]);
   if (!k){ printf("%d\n",maxim);k = 1;}
   printf("%d ",i);
}
int main()
{
   freopen("subsir2.in","r",stdin);
   freopen("subsir2.out","w",stdout);
   int i, j;
   long val = 0;

   scanf("%ld",&n);
   for (i = 1; i <= n; i++) scanf("%ld", v + i);
   best[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))
	 {
	     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;
   }
   afis(val);
   return 0;
}