Cod sursa(job #2418162)

Utilizator lucametehauDart Monkey lucametehau Data 3 mai 2019 21:46:18
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>

using namespace std;

ifstream cin ("subsir2.in");
ofstream cout ("subsir2.out");

int n;

int v[5005], dp[5005];

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++)
    cin >> v[i], dp[i] = 5001;
  dp[n] = 1;
  for(int i = n - 1; i >= 1; i--) {
    int mn = 1000000;
    for(int j = i + 1; j <= n; j++) {
      if(v[i] <= v[j] && v[j] < mn) {
        mn = v[j];
        dp[i] = min(dp[i], dp[j] + 1);
      }
    }
    if(dp[i] == 5001)
      dp[i] = 1;
  }
  int mn2 = 1000000, sol = 5000;
  for(int i = 1; i <= n; i++) {
    if(v[i] < mn2) {
      mn2 = v[i];
      sol = min(sol, dp[i]);
    }
  }
  cout << sol << "\n";
  int poz = 0, lst = -1000000;
  while(sol) {
    int val1 = 1000000, val2 = 1000000;
    for(int i = poz + 1; i <= n; i++) {
      if(dp[i] == sol && lst <= v[i] && v[i] < val1) {
        val1 = val2 = v[i];
        poz = i;
      } else if(lst <= v[i] && v[i] < val1)
        val1 = v[i];
    }
    cout << poz << " ";
    lst = v[poz];
    sol--;
  }
  return 0;
}