Cod sursa(job #1024032)

Utilizator dropsdrop source drops Data 8 noiembrie 2013 01:02:37
Problema Subsir 2 Scor 96
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX 5001
#define INF 0xFFFFFF

int N, K, Val[MAX], Best[MAX], Prec[MAX], Sol[2][MAX], Lmin;

bool LexicographicalLower() {
    for (int i = 1; i <= Lmin; i++) {
        if (Val[Sol[1][i]] < Val[Sol[0][i]]) return 1;
        if (Val[Sol[1][i]] > Val[Sol[0][i]]) return 0;
    }
    return 0;
}

void GetTrace(int N, int K) {
    if (K != 0) {
        GetTrace(N - 1, Prec[K]);
        Sol[1][N] = K;
    }
}

int main(){
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);

    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &Val[i]);
    }
    Val[0] = -INF;
    Best[0] = 0;
    for (int i = 1; i <= N; i++) {
        Best[i] = INF;
        K = -INF - 1;
        for (int j = i - 1; j >= 0; j--) {
            if (Val[j] <= Val[i] && Val[j] > K) {
                if (Best[j] + 1 < Best[i]) {
                    Best[i] = Best[j] + 1;
                    Prec[i] = j;
                } else if (Best[j] + 1 == Best[i] && (Prec[i] != 0 && Val[j] <= Val[Prec[i]])) {
                    Prec[i] = j;
                }
                if (Val[j] <= Val[i]) {
                    K = max(K, Val[j]);
                }
            }
        }
    }
    //for (int i = 1; i <= N; i++) printf("%d ", Best[i]); printf("\n");
    K = -INF;
    Lmin = INF;
    for (int i = N; i >= 1; i--) {
        if (Val[i] > K) {
            if(Best[i] < Lmin) {
                Lmin = Best[i];
                GetTrace(Lmin, i);
                for (int i = 1; i <= Lmin; i++) Sol[0][i] = Sol[1][i];
            } else if (Best[i] == Lmin) {
                GetTrace(Lmin, i);
                if (LexicographicalLower()) {
                    for (int i = 1; i <= Lmin; i++) Sol[0][i] = Sol[1][i];
                }
            }
        }
        K = max(K, Val[i]);
    }
    printf("%d\n", Lmin);
    if (Lmin == 1) return -1;
    for (int i = 1; i <= Lmin; i++) printf("%d ", Sol[0][i]);
    return 0;
}