Cod sursa(job #1521854)

Utilizator tudorcomanTudor Coman tudorcoman Data 10 noiembrie 2015 21:45:33
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb

/// dp[i] = cel mai scurt subsir maximal ce se termina pe pozitia i

#include <cstdio>
const int maxN = 5000;
const int inf = 1 << 20;
int N, v[maxN + 2], next[maxN + 2], dp[maxN + 2];

int main() {
  freopen("subsir2.in", "r", stdin);
  freopen("subsir2.out", "w", stdout);
  scanf("%d", &N);
  for(register int i = 1; i <= N; ++ i)
    scanf("%d", &v[i]);
  for(register int i = N; i > 0; -- i) {
    int pos;
    pos = next[i] = -1;
    dp[i] = inf;
    for(register int j = i + 1; j <= N; ++ j) {
      if(v[i] <= v[j]) {
        if(pos == -1 or v[pos] > v[j])
          pos = j;
        if(dp[i] > dp[pos] + 1 or (dp[i] == dp[pos] + 1 and v[pos] < v[next[i]])) { /// fac minim (inclusiv lexicografic)
          dp[i] = dp[pos] + 1;
          next[i] = pos;
        }
      }
    }
    if(dp[i] == inf)
      dp[i] = 1;
  }

  int pos = 1; int Min = v[1];
  for(register int i = 2; i <= N; ++ i) {
    if(v[i] < Min) {
      v[i] = Min;
      if(dp[i] < dp[pos] or (dp[i] == dp[pos] and v[i] < v[pos]))
        pos = i;
    }
  }
  printf("%d\n", dp[pos]);
  while(pos != -1) {
    printf("%d ", pos);
    pos = next[pos];
  }
  return 0;
}