Cod sursa(job #2205891)

Utilizator Hidden.bdBurlacu Doru Hidden.bd Data 20 mai 2018 15:53:56
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 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;

    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;

        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;
    }

    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;
}