Cod sursa(job #1660762)

Utilizator horatiudumhoratiu horatiudum Data 23 martie 2016 13:30:49
Problema Subsir 2 Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.29 kb
// lexicographical_compare example
#include <iostream>     // std::cout, std::boolalpha
#include <algorithm>    // std::lexicographical_compare
#include <cctype>       // std::tolower
#include <sstream>
#include <string>
#include <vector>
#include <stdio.h>
#include <cstring> // for C strings
#include <fstream>
#include <set>
#include <list>
using namespace std;
#define MAX 5002

ifstream fin("subsir2.in");
ofstream out("subsir2.out");
//#define MAX 8

int n = MAX;

//int x[] = {24, 12, 15, 15, 8, 19};
//int x[] = {1, 3, 6, 2, 5, 4};
//int x[] = {1, 6, 9, 5, 4, 8, 7};
//int x[] = {48, 1, 3, 6, 2, 5, 4, -15};
struct rest{
    int pozOk;
    int idxRamas;
};
int LIS[MAX],poz[MAX],sir[MAX],x[MAX],SIS[MAX],NEXT[MAX],FRONT[MAX];
int main()
{
    int i=0;
    int j=0;
    int minVal=0;
    fin >> n;
    for(i=1;i<=n;i++) {
      //LIS[i]=1;
      //poz[i]=-1;
      fin >> x[i];
    }



//celui mai scurt subşir crescător (SIS – Shortest Increasing Substring)
/*
    int infinit=10000;
    int val=0;
    int poz1=0;
    int min = 0;
    poz[n-1] = 1;
    for (i = n-2; i>=0; i--){
        min = 0;
        poz1 = n-1;
        val = infinit;
        //NEXT[i]=0;
        for (j= i+1; j< n; j++) {
            if (min<=poz[j] && x[i] <=x[j] && x[j]<val) {
                    min = poz[j];
                    poz1 = j;
                    val = x[j];
                    //NEXT[i]=j;
            }
        }
        if (poz1 <= n-1) {
            poz[i] = 1 + min;
        } else {
            poz[i] = 1;
        }
    }
    min = poz[0];
    for (i = 1; i<n; i++) {
      if (min > poz[i]) min = poz[i];
    }
    //write min
*/


//ok max
/*
    for(i=n-1;i>=0;i--) {
      max=0;
      if(var==1) {
        LIS[i]=0;
        poz[i]=-2;
      }
      var=0;
      for(j=0;j<i;j++) {
        if(x[j]<x[i] && max<x[j]) {
            poz[i]=j;
            max=x[j];
            k++;
            LIS[i]=k;//1+LIS[j];
            //if(j==0) {
            var=1;
            //}
        }
        if(i-1==j) {
            LIS[i]=k+1;
        }
      }

      k=0;

      if(Lmax<LIS[i]) {
         Lmax=LIS[i];
      }
      if(Lmin>LIS[i] && LIS[i]!=0) {
         Lmin=LIS[i];
      }
     }
*/

    //int lung=n;
    //int k=0;
    int minLen=0;
    int min=n;
    LIS[n]=1;
    poz[n]=-1;
    for (i = n-1; i>=0; i--){
          LIS[i]=1;
          poz[i]=-1;
          minVal=-2000000;
          minLen=1;
          for (j=i+1; j<=n; j++) {
            if(i!=0 && x[i]<x[j]) {
                FRONT[j]=1;
                if(minVal<x[j] && poz[i]==-1) {
                    poz[i]=j;
                    minVal=x[j];
                    LIS[i]=1+LIS[j];
                    minLen=LIS[i];
                } else if (minVal>x[j]) {
                    minVal=x[j];
                    if(minLen>LIS[j]) {
                        poz[i]=j;
                        LIS[i]=1+LIS[j];
                        minLen=LIS[i];
                    }
                }
            }
            if(i==0 && FRONT[j]==0 && min>LIS[j]) {
                min=LIS[j];
                poz[0]=j;
                LIS[0]=LIS[j];
            }
          }
     }

        out << min << '\n';
        i = poz[0];
        out << i << " ";
        while (poz[i] != -1)
        {
            -- min;
            out << poz[i] << " ";
            i = poz[i];
        }
    return 0;
}