Cod sursa(job #87278)

Utilizator gigi_becaliGigi Becali gigi_becali Data 26 septembrie 2007 21:51:24
Problema Subsir 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 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;
         dp[i]=oo;
      for(j=i+1;j<=n;++j)
	if(a[i]<=a[j])
	  {
	    
	    if(dp[i]>dp[j]+1)
	      {
		if(a[j]<min)dp[i]=dp[j]+1, t[i]=j, p=j;
	      }
	    else 
	      if(dp[i]==dp[j]+1)
		{
		  if(a[j]<min && a[j]<a[p]) dp[i]=dp[j]+1, t[i]=j, p=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;
	}
    }
  //for(i=1;i<=n;++i)printf("%d ", dp[i]);

  int poz=1, max=dp[1];
  for(i=2;i<=n;++i) if(max<dp[i] && dp[i]!=oo)max=dp[i], poz=i;
  else if(max==dp[i]) if(a[i]<a[poz]) 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;
}