Cod sursa(job #2782192)

Utilizator euyoTukanul euyo Data 11 octombrie 2021 20:49:57
Problema Subsir 2 Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

const int MAXN = 5005; 
const int INF = (int)1e6 + 1;

int v[MAXN], ok_last[MAXN];
int dp[MAXN], pre[MAXN];
vector<int> sol;

int main() {
  int n, mx = -INF;

  fin >> n;
  for ( int i = 1; i <= n; ++i ) {
	fin >> v[i];
  }
  for ( int i = n; i >= 1; --i ) {
	ok_last[i] = (v[i] > mx);
    mx = max( mx, v[i] ); 	
  }
  for ( int i = 1; i <= n; ++i ) {
	mx = -INF;

	int pos = i, val = INF;
	for ( int j = i - 1; j >= 1; --j ) {
      if ( v[j] <= v[i] && mx < v[j] ) {
		if ( val > dp[j] + 1 ) {
	      val = dp[j] + 1;
		  pos = j;
		} else if ( val == dp[j] + 1 && v[pos] > v[j] ) {
          pos = j;
		}
	  }
	  if ( v[j] <= v[i] ) {
	    mx = max( mx, v[j] );
	  }
  	}
	dp[i] = val;
	pre[i] = pos;

    if ( dp[i] == INF ) {
	  dp[i] = 1;
    }
  }
  int res = INF, ind = 0;
  for ( int i = 1; i <= n; ++i ) {
	if ( ok_last[i] ) {
	  if ( res > dp[i] ) {
		res = dp[i];
		ind = i;
	  } else if ( res == dp[i] && v[ind] > v[i] ) {
		ind = i;
	  }
	}
  }
  fout << res << "\n";
  while ( pre[ind] != ind ) {
    sol.push_back( ind );
	ind = pre[ind];
  }
  sol.push_back( ind );
  for ( int i = sol.size() - 1; i >= 0; --i ) {
	fout << sol[i] << " ";
  }
  fin.close();
  fout.close();
  return 0;
}