Cod sursa(job #583492)

Utilizator david95szabo david emanuel david95 Data 20 aprilie 2011 16:38:10
Problema Subsir 2 Scor 2
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#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;
}