Cod sursa(job #973052)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 13 iulie 2013 11:42:52
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<stdio.h>
#include<vector>
#include<algorithm>

#define NMAX 5007

using namespace std;

vector < int > SOL;
int best[NMAX], a[NMAX], n, MAX, poz, last_poz;

inline int max(int a, int b)
{
    if(a > b)
        return a;
    return b;
}

int main(){
    freopen("subsir2.in", "r", stdin);
    freopen("subsir2.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i)
        scanf("%d", &a[i]);
    best[1] = 1;
    for(int i = 2; i <= n; ++ i){
        for(int j = 1; j < i; ++ j)
            if(a[i] >= a[j])
                best[i] = max(best[i], best[j] + 1);
        MAX = max(MAX, best[i]);
    }
    int Number = 20000000;
    for(int i = 1; i <= n; ++ i)
        if(best[i] == MAX)
            if(Number >= a[i]){
                Number = a[i];
                poz = i;
            }
    printf("%d\n", MAX);
    SOL.push_back(poz);
    -- MAX;
     while(MAX > 0)
    {
        last_poz = poz;
        int Number2 = 2000000000, poz = 0;
        for(int i = last_poz; i >= 1; -- i)
            if(best[i] == MAX && a[i] <= Number)
                if(Number2 >= a[i]){
                    Number2 = a[i];
                    poz = i;
                }
        SOL.push_back(poz);
        Number = Number2;
        -- MAX;
    }
    reverse(SOL.begin(), SOL.end());
    for(int i = 0; i < SOL.size(); ++ i)
        printf("%d ", SOL[i]);
    return 0;
}