Cod sursa(job #1023762)

Utilizator dropsdrop source drops Data 7 noiembrie 2013 18:12:08
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX 5001

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

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

bool LexicographicalLower() {
    for (int i = 0; i < K; 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;
}

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

    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &Val[i]);
    }

    Best[0] = 1;
    for (int i = 0; i < N; i++) {
        Best[i] = 1;
        Prec[i] = -1;
        for (int j = i - 1; j >= 0; j--)
            if (Val[j] <= Val[i] && Best[j] + 1 > Best[i]) {
                Best[i] = Best[j] + 1;
                Prec[i] = j;
            } else if (Val[j] <= Val[i] && Best[j] + 1 == Best[i] && (Prec[i] == -1 || Val[j] < Val[Prec[i]])) {
                Prec[i] = j;
            }
        if (Best[i] > K) K = Best[i];   // subsir maxim
    }
    FirstSolution = 0;
    for (int i = 0; i < N; i++)
        if (Best[i] == K) {
            GetTrace(K - 1, i);    // extrag sirul
            if (!FirstSolution || LexicographicalLower()) {
                for (int j = 0; j < K; j++) Sol[0][j] = Sol[1][j];
                FirstSolution = 1;
            }
        }
   // for (int i = 0; i < N; i++) printf("%d ", Best[i]); printf("\n");
    printf("%d\n", K);
    for (int i = 0; i < K; i++) printf("%d ", Sol[0][i] + 1);
    return 0;
}