Cod sursa(job #1394516)

Utilizator hrazvanHarsan Razvan hrazvan Data 20 martie 2015 13:06:31
Problema Subsir 2 Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>
#define MAXN 5000
#define INF 2000000000
FILE *out;
int v[MAXN + 1], d[MAXN + 1], next[MAXN + 1];

int main(){
  FILE *in = fopen("subsir2.in", "r");
  int n, i;
  fscanf(in, "%d", &n);
  v[0] = -INF;
  for(i = 1; i <= n; i++)
    fscanf(in, "%d", &v[i]);
  fclose(in);
  int j, min;
  for(i = n; i >= 0; i--){
    min = INF;
    for(j = i + 1; j <= n ; j++){
      if(v[j] < min && v[j] >= v[i]){
        if(d[i] == 0 || d[i] > d[j] + 1 || (next[i] != 0 && d[i] == d[j] + 1 && v[j] < v[next[i]])){
          d[i] = d[j] + 1;
          next[i] = j;
        }
        min = v[j];
      }
    }
    if(d[i] == 0){
      d[i] = 1;
      next[i] = -1;
    }
  }
  out = fopen("subsir2.out", "w");
  fprintf(out, "%d\n", d[0] - 1);
  int poz = next[0];
  while(poz != -1){
    fprintf(out, "%d ", poz);
    poz = next[poz];
  }
  fclose(out);
  return 0;
}