Cod sursa(job #1558877)

Utilizator stoianmihailStoian Mihail stoianmihail Data 29 decembrie 2015 18:33:17
Problema Subsir 2 Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
#include <limits.h>

#define Nadejde 5000

int N;
int d[Nadejde + 1];
int val[Nadejde + 1];
int parent[Nadejde + 1];

int main(void) {
  int i, j, pos, min, curr;
  FILE *f = fopen("subsir2.in", "r");

  /* Citirea datelor. */
  fscanf(f, "%d", &N);
  for (i = 1; i <= N; i++) {
    fscanf(f, "%d", &val[i]);
  }
  val[0] = INT_MIN;
  fclose(f);

  /* Calcularea solutiei. */
  for (i = N; i >= 0; i--) {
    min = d[i] = INT_MAX;
    for (j = i + 1; j <= N; j++) {
      if ((val[j] < min) && (val[i] <= val[j])) {
        min = val[j];
        curr = d[j] + 1;

        /* Cautam minimul lexicografic. */
        if ((d[i] == curr) && (val[j] < val[parent[i]])) {
          parent[i] = j;
        }
        if (curr < d[i]) {
          d[i] = curr;
          parent[i] = j;
        }
      }
    }
    if (d[i] == INT_MAX) {
      d[i] = 1;
      parent[i] = i;
    }
  }

  /* Afisarea solutiei. */
  freopen("subsir2.out", "w", stdout);
  fprintf(stdout, "%d\n", d[0] - 1);
  for (pos = 0; pos != parent[pos]; pos = parent[pos]) {
    printf("%d ", parent[pos]);
  }
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}