Cod sursa(job #2208131)

Utilizator Hidden.bdBurlacu Doru Hidden.bd Data 28 mai 2018 13:24:01
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iomanip>
 
#define PI 3.141592653589793
 
using namespace std;
 
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
 
//#define fin cin
//#define fout cout

int dp[5002], poz[5002], v[5002];

int main(){

	int n;

	fin >> n;

	for( int i = 1 ; i <= n ; ++i ) fin >> v[i];
	v[0] = -2000000000;
	
	int minim;
	for( int i = n ; i >= 0 ; --i ){
		dp[i] = minim = 2e9;
		for( int j = i + 1 ; j <= n ; ++j ){
			if( v[j] >= v[i] && dp[j] <= dp[i] && v[j] < minim ){
				dp[i] = dp[j];
				poz[i] = j;
			}
			if( v[j] < minim && v[j] >= v[i] ) minim = v[j];
		}

		if( !poz[i] ){
			poz[i] = n + 1;
			dp[i] = 0;
		}
		++dp[i];
	}

	fout << dp[0] - 1 << "\n";
	int i = 0;
	while( i <= n ){
		if( poz[i] <= n ) fout << poz[i] << " ";
		i = poz[i];
	}
	
}