Cod sursa(job #2214893)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 20 iunie 2018 14:50:00
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>

using namespace std;

ifstream fin ("subsir2.in");
ofstream fout ("subsir2.out");

const int Dim = 5001;
int D[Dim], T[Dim],n,A[Dim],Used[Dim];

void Dynamic();
void Afis(int poz);

int main() {
	
	fin >> n;
	for ( int i = 1; i <= n; ++i)
		fin >> A[i];
	Dynamic();
	int mi = 0x3f3f3f3f,poz;
	for ( int i = 1; i <= n; ++i) 
		if ( mi > D[i] and !Used[i] ) {
			mi = D[i];
			poz = i;
			}
	fout << mi << "\n";
	Afis(poz);
}

void Afis(int poz) {
	
	fout << poz << " " ;
	if ( T[poz] == 0)	return;
	Afis(T[poz]);
}

void Dynamic() {
	
	for ( int i = n; i >= 1; --i) {
		D[i] = 0x3f3f3f3f;
		int mi = 0x3f3f3f3f, miA = 0x3f3f3f3f,poz;
		for ( int j = i + 1; j <= n; ++j) {
			if ( A[j] >= A[i] and A[j] < mi and D[j] < miA) {
				miA = D[j];
				Used[j] = 1;
				poz = j;
				}
			else
				if ( A[j] >= A[i] and A[j] < mi and D[j] == miA and A[poz] > A[j] )
					poz = j,Used[j] = 1;
			if ( A[j] >= A[i] and mi > A[j] ) 
				mi = A[j];
			}
		D[i] = miA + 1;
		T[i] = poz;
		if ( miA == 0x3f3f3f3f )
			D[i] = 1, T[i] = 0;
		}
}