Cod sursa(job #19182)

Utilizator gigi_becaliGigi Becali gigi_becali Data 18 februarie 2007 20:50:27
Problema Subsir 2 Scor 78
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
#define maxn 1<<13
#define oo 0x3f3f3f3f

int n, a[maxn], bst[maxn], t[maxn], rez=oo, poz, min;
char ok[maxn];

void citire()
{
  int i;
  freopen("subsir2.in", "r", stdin);
  freopen("subsir2.out", "w",stdout);
  scanf("%d\n", &n);
  for(i=0;i<n;i++)
    {
      scanf("%d ", a+i);
      if(min<=a[i]) continue;
      ok[i]=1;
      min=a[i];
    }
}

int main()
{
  int i, j, min;
  citire();
  for(i=n-1;i>=0;i--)
    {
      bst[i]=min=oo;
      t[i]=-1;
      for(j=i+1;j<n;j++)
	{
	  if(a[j]<a[i]) continue;
	  if(min>a[j]&&(bst[i]>bst[j]+1||bst[i]==bst[j]+1&&a[j]<a[t[i]]))
	    {
	      bst[i]=bst[j]+1; t[i]=j;
	    }
	  if(min>a[j]) min=a[j];
	}
      if(bst[i]==oo)
	{
	  bst[i]=1;
	  t[i]=i;
	}
      if(ok[i]&&(rez>bst[i]||(rez=bst[i]&&a[i]<a[poz])))
	{
	  rez=bst[i]; poz=i;
	}
    }
  rez=0;
  for(i=poz;i!=t[i];i=t[i]) rez++;
      printf("%d\n", rez+1);
      for(i=poz;i!=t[i];i=t[i]) printf("%d ", i+1);
      printf("%d\n", i+1);
      return 0;
  }