Pagini recente » Cod sursa (job #2868372) | Cod sursa (job #75239) | Cod sursa (job #89924) | Cod sursa (job #1519409) | Cod sursa (job #583492)
Cod sursa(job #583492)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
#define DIM 100001
int L[DIM], ANT[DIM], SOL[DIM], SF[DIM];
int n, a[DIM];
int main()
{
int smin = 1000000, i, j,poz,k,min,p;
fin >> n;
for ( i = 0; i < n; ++i )
fin >> a[i];
for ( i = 0; i < n; ++i )
{
ANT[i] = -1;
SF[i] = 1;
L[i] = 1;
}
for ( i = 0; i < n; ++i )
{
min = 10000;
for ( j = 0; j < i; ++j )
if ( a[i] > a[j] )
{
if ( L[j] < min )
{
min = L[j];
p = j;
}
ANT[i] = p;
L[i] = L[p] + 1;
SF[j] = 0;
}
}
for ( i = 0; i < n; ++i )
if ( smin > L[i] && SF[i]==1 )
{ smin = L[i];
poz=i;
}
fout << smin <<endl;
i = poz;
k = 0;
while ( ANT[i] != -1 )
{
SOL[k] = i + 1;
k++;
i=ANT[i];
}
SOL[k] = i + 1;
for ( i = k; i >= 0; i-- )
fout << SOL[i] << " ";
fin.close();
fout.close();
return 0;
}