Cod sursa(job #2208128)

Utilizator Hidden.bdBurlacu Doru Hidden.bd Data 28 mai 2018 13:17:47
Problema Subsir 2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 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;
}