Cod sursa(job #2206898)

Utilizator Hidden.bdBurlacu Doru Hidden.bd Data 24 mai 2018 10:36:37
Problema Subsir 2 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 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];
  
int main(){
  
    int n;
    int v[5002], poz[5002], afis[5002];
    int crr_max = 0;
    int minDP, minDPval;
    int DPminTOT = 5002;
    int start;
    v[0] = -1000000;
 
    fin >> n;
    for( int i = 1 ; i <= n ; ++i ){
        fin >> v[i];
    }
 
    for( int i = 1 ; i <= n ; ++i ){
        minDP = 5002;
        minDPval = 1000002;
        crr_max = -1000002;

        //if( i == 3 ){
        	//for( int j = 1 ; j <= 3 ; ++j ) fout << dp[j] << " ";
        //}
 
        for( int j = i - 1 ; j >= 0 ; --j ){
 
            if( v[j] < v[i] && v[j] > crr_max ){
                crr_max = v[j];
 
                if( dp[j] < minDP && v[j] < minDPval ){
                    minDP = dp[j];
                    minDPval = v[j];
                    poz[i] = j;
                }
 
            }
        }
        dp[i] = minDP + 1;
    }
 	//fout << dp[12] << "\n";
    crr_max = -1000002;
    for( int i = n ; i >= 1 ; --i ){
 
        if( v[i] > crr_max ){
 
            crr_max = v[i];
 
            if( dp[i] < DPminTOT ){
                DPminTOT = dp[i];
                start = i;
            }
 
        }
 
    }
 
    afis[0] = 0;
 
    fout << DPminTOT << "\n";
    for( int i = start ; i != 0 ; i = poz[i] ) afis[++afis[0]] = i;
 
    for( int i = afis[0] ; i >= 1 ; --i ) fout << afis[i] << " ";
 
 
    return 0;
}