Cod sursa(job #87264)

Utilizator gigi_becaliGigi Becali gigi_becali Data 26 septembrie 2007 21:35:33
Problema Subsir 2 Scor 42
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <cstdio>
#define maxn 5001
#define oo 0x3f3f3f3f

int a[maxn], dp[maxn], t[maxn];
int Q[maxn], nq;
int n;

int main()
{
  freopen("subsir2.in","r",stdin);
  scanf("%d\n", &n);
  int i, j;
  for(i=1;i<=n;++i)scanf("%d ", a+i);

  dp[n]=1;
  int min, p, Dp;
  for(i=n-1;i>=1;--i)
    {
      min=oo;
      Dp=oo;
      for(j=i+1;j<=n;++j)
	if(a[i]<=a[j])
	  {
	   
	    if(min>=a[j]) min=a[j], p=j, Dp=dp[j];
	    else if(min==a[j] && dp[j]<Dp){ min=a[j], p=j, Dp=dp[j];}
	  }
      if(min!=oo)
	{
	  dp[i]=dp[p]+1;
	  t[i]=p;
	}
    }

  int poz=1, max=dp[1];
  for(i=2;i<=n;++i) if(max<dp[i])max=dp[i], poz=i;

  for(i=poz;i!=0;i=t[i]) Q[++nq]=i;

  freopen("subsir2.out","w",stdout);
  printf("%d\n", nq);
  for(i=1;i<=nq;++i)printf("%d ", Q[i]);
  printf("\n");
  return 0;
}