Pagini recente » Cod sursa (job #1329354) | Cod sursa (job #176230) | Cod sursa (job #444092) | Cod sursa (job #749126) | Cod sursa (job #1666177)
// 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 5005
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];
}
if (minVal>x[j]) {
minVal=x[j];
if(minLen>LIS[j]) {
poz[i]=j;
LIS[i]=1+LIS[j];
minLen=LIS[i];
}
}
if (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;
}