Cod sursa(job #600409)

Utilizator Smaug-Andrei C. Smaug- Data 1 iulie 2011 16:36:49
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <cstdio>

#define MAXN 5005
#define INF (1<<30)

int main(){

  freopen("subsir2.in", "r", stdin);
  freopen("subsir2.out", "w", stdout);
 
  int N, i, j, A[MAXN], L[MAXN], P[MAXN], minv, minp, minl;

  scanf("%d", &N);
  for(i=1; i<=N; i++)
    scanf("%d", A+i);

  for(i=N; i; i--){
    minv=INF; minp=0; L[i]=INF;
    for(j=i+1; j<=N; j++){
      if(A[j]<minv && A[j] >= A[i]){
	minv=A[j];
	if(L[j]+1 < L[i])
	  L[i]=L[j]+1, minp=j;
	else if(L[j]+1==L[i] && A[j]<A[minp])
	  minp=j;
      }
    }
    if(L[i]==INF)
      L[i]=1;
    P[i]=minp;
  }

  minv=INF; minp=0; minl=INF;
  for(i=1; i<=N; i++)
    if(A[i] < minv){
      minv=A[i];
      if(L[i] < minl)
	minl=L[i], minp=i;
      else if(L[i] == minl)
	minp=i;
    }

  printf("%d\n", minl);
  for(i=minp; i; i=P[i])
    printf("%d ", i);
  printf("\n");

  return 0;

}