Cod sursa(job #2782199)

Utilizator euyoTukanul euyo Data 11 octombrie 2021 21:05:13
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 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_first[MAXN];
int dp[MAXN], nxt[MAXN];

int main() {
  int n, mn = INF;

  fin >> n;
  for ( int i = 1; i <= n; ++i ) {
	fin >> v[i];
  }
  for ( int i = 1; i <= n; ++i ) {
	ok_first[i] = (v[i] < mn);
    mn = min( mn, v[i] ); 	
  }
  for ( int i = n; i >= 1; --i ) {
	mn = INF;

	int pos = i, val = INF;
	for ( int j = i + 1; j <= n; ++j ) {
      if ( v[i] <= v[j] && mn > 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[i] <= v[j] ) {
	    mn = min( mn, v[j] );
	  }
  	}
	dp[i] = val;
	nxt[i] = pos;

    if ( dp[i] == INF ) {
	  dp[i] = 1;
    }
  }
  int res = INF, ind = 1;
  for ( int i = 1; i <= n; ++i ) {
	if ( ok_first[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 ( nxt[ind] != ind ) {
    fout << ind << " ";
	ind = nxt[ind];
  }
  fout << ind << " ";
  fin.close();
  fout.close();
  return 0;
}