Cod sursa(job #2775234)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 15 septembrie 2021 02:17:07
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("subsir2.in");
ofstream out("subsir2.out");

const int inf = (int)1e9;
const int maxN = (int)5e3;

int n;

int v[maxN + 5];

int maximalLen[maxN + 5];

int dad[maxN + 5];

bool canBeFirst[maxN + 5];

int main() {
  in >> n;
  for (int i = 1; i <= n; i++) {
    in >> v[i];
  }
  /// maximalLen[i] = cel mai scurt subsir crescator maximal
  ///                 care incepe la i

  /// maximalLen[i] = min(maximalLen[j] + 1) | j > i, v[j] > v[i]
  ///                                        | v[j] = min(v[k]), k = [i, j]
  fill(canBeFirst + 1, canBeFirst + n + 1, true);
  for (int i = n; i >= 1; i--) {
    int minValue = inf;
    maximalLen[i] = inf;
    for (int j = i + 1; j <= n; j++) {
      if (v[j] >= v[i]) {
        canBeFirst[j] = false;
      }
      if (v[j] < minValue && v[j] >= v[i]) {
        minValue = v[j];
        if (maximalLen[i] >= maximalLen[j] + 1) {
          maximalLen[i] = maximalLen[j] + 1;
          dad[i] = j;
        }
      }
    }
    if (maximalLen[i] == inf) {
      maximalLen[i] = 1;
    }
  }
  int posMaximalLen = 0;
  maximalLen[0] = inf;
  for (int i = 1; i <= n; i++) {
    if (canBeFirst[i]) {
      if (maximalLen[i] < maximalLen[posMaximalLen]) {
        posMaximalLen = i;
      } else if (maximalLen[i] == maximalLen[posMaximalLen] && v[i] < v[posMaximalLen]) {
        posMaximalLen = i;
      }
    }
  }
  vector<int> result;
  while (posMaximalLen) {
    result.push_back(posMaximalLen);
    posMaximalLen = dad[posMaximalLen];
  }
  out << (int)result.size() << "\n";
  for (int val : result) {
    out << val << " ";
  }
  return 0;
}