Pagini recente » Cod sursa (job #2514927) | Cod sursa (job #3222254) | Cod sursa (job #1796466) | Cod sursa (job #3231079) | Cod sursa (job #1659909)
// 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 5001
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;
};
set<int> myset;
set<int>::iterator it;
set<int>::reverse_iterator rit;
int LIS[MAX],poz[MAX],sir[MAX],x[MAX],SIS[MAX],NEXT[MAX],FRONT[MAX];
int main()
{
//LIS[n-1] = 1;
int i=0;
int j=0;
//int max=0;
int minVal=0;
//int k=0;
//int Lmax=0;
//int Lmin=100000;
//int var=0;
fin >> n;
for(i=0;i<n;i++) {
myset.insert(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;
for (i = n-2; i>=0; i--){
minVal=-2000000;
minLen=1;
for (j=i+1; j< n; j++) {
if(x[i]<x[j]) {
myset.erase(j);
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];
}
}
}
}
}
//k=0;
for (rit=myset.rbegin(); rit != myset.rend(); ++rit) {
//for (it=myset.end(); it==myset.begin(); --it) {
if(min>=LIS[*rit]) {
min=LIS[*rit];
//k=*rit;
} //else {
// myset.erase(*rit--);
//}
}
if(LIS[0]>min && myset.size()>1) myset.erase(0);
int valTmp=-2000000;
k=0;
for (it=myset.begin(); it!=myset.end(); ++it) {
if(min!=LIS[*it]) {
myset.erase(*it);
continue;
}
if(valTmp==-2000000) {
valTmp=x[*it];
} else if(valTmp>x[*it]) {
myset.erase(k);
} else {
myset.erase(*it);
}
k=*it;
}
out << min << '\n';
k=*myset.begin();
out << k+1 << " ";
for (j=0; j<min-1; j++) {
out << poz[k]+1 << " ";
if(poz[k]==-1) {
break;
}
k=poz[k];
}
//out << "\n";
/*for (it=myset.begin(); it!=myset.end(); ++it) {
int k=*it;
for (j=0; j<min; j++) {
cout << x[k] << " ";
if(poz[k]==-1) {
break;
}
k=poz[k];
}
cout << "\n";
}*/
return 0;
}