Cod sursa(job #1999540)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 11 iulie 2017 14:00:58
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int v[100001], n; //date de intrare
int lgSecv[100001];//lgSecv[i] - lungimea secveentei care se termina in v[i];
int rezultat[100001];//array cu solutia finala
int lgMax, poz;

void citire(){
  in >> n;
  for(int i = 1; i <= n; i++)
    in >> v[i];
}

void rezolvare(){
  for(int i = n; i >= 1; i--){
    lgSecv[i] = 1;
    for(int j = i + 1; j <= n; j++)
      if(v[i] < v[j] && lgSecv[i] < lgSecv[j] + 1)
        lgSecv[i] = lgSecv[j] + 1;
    if(lgSecv[i] >= lgMax){
      lgMax = lgSecv[i];
      poz = i;
    }
  }

  int LgMinima = n + 1, pozMin;
  for(int i =1; i<=n; i++){
    bool ok = true;
    for(int j = i - 1; j >= 1; j--)
      if(v[j] < v[i] && lgSecv[i] + 1 == lgSecv[j]){
        ok = false;
        break;
      }
    if(ok == true && LgMinima > lgSecv[i]){
      LgMinima = lgSecv[i];
      poz = i;
    }
  }
  if(LgMinima == n + 1){
    LgMinima = 1;
    poz = 1;
  }

  int L = LgMinima;
  int plec = poz;
  int aux = 0;

  while(L != 0){
    aux = 0;
    for(int i = plec; i <= n; i++){
      if(aux == 0 && L == lgSecv[i]){
        aux = plec = i;
      }
      if(L == lgSecv[i] && v[i] < v[aux])
        plec = i;
    }
    rezultat[++rezultat[0]] = plec;
    L -- ;
  }
  out << LgMinima << '\n';
  for(int i = 1; i <= rezultat[0]; i++)
    out << rezultat[i] << ' ';
}

int main(){
  citire();
  rezolvare();
  return 0;
}