Cod sursa(job #1500242)

Utilizator refugiatBoni Daniel Stefan refugiat Data 11 octombrie 2015 17:22:12
Problema Subsir 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb

#include<iostream>
#include<fstream>
#include<bitset>
using namespace std;

const int NMAX = 5000;

int v[1+NMAX];
int succesor[1+NMAX], lungime[1+NMAX];
bitset<1+NMAX> extins;

int main()
{
  ifstream si;
  si.open("subsir2.in");
  ofstream so;
  so.open("subsir2.out");
  int n;
  si>>n;
  for(int i=1; i<=n; ++i)
    si>>v[i];

  for(int i=n; i>0; --i)
  {
    int k = -1; // cel mai mic element mai mare ca v[i] si mai mic ca v[j]
    lungime[i] = NMAX+1;
    for(int j=i+1; j<=n; ++j)
    {
      if(v[i] <= v[j] && (k == -1 || k > v[j]))
      {
        extins[j]=1;
        if(lungime[j]+1 < lungime[i])
        {
          lungime[i] = lungime[j] + 1;
          succesor[i] = j;
        } else if(lungime[j] + 1 == lungime[i])
          if(v[j] < v[succesor[i]])
            succesor[i]=j;

        if(k == -1 || v[j] < k)
          k = v[j];
      }
    }
    if(lungime[i] == NMAX+1)
      lungime[i] = 1;
  }

  int sol = lungime[1], poz = 1;
  for(int i=2; i<=n; ++i)
  {
    if(!extins[i])
    {
      if(lungime[i] < sol)
      {
        sol=lungime[i];
        poz = i;
      } else if(lungime[i] == sol)
      {
        if(v[i] < v[poz])
          poz = i;
      }
    }
  }

  so<<sol<<'\n';
  while(poz != 0)
  {
    so<<poz<<' ';
    poz=succesor[poz];
  }
  so<<'\n';

  return 0;
}