Cod sursa(job #1867642)

Utilizator giotoPopescu Ioan gioto Data 4 februarie 2017 11:28:36
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int n, a[5002], best[5002], last[5002], Next[5002], b[5002], c[5002], first[5002];
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]);
    for(int i = n; i >= 1 ; --i){
        int Min = 1000005; best[i] = 1000005;
        for(int j = i + 1; j <= n ; ++j){
            if(Min > a[j] && a[i] <= a[j]){
                Min = a[j];
                if(best[i] > best[j] + 1){
                    best[i] = best[j] + 1;
                    last[i] = j;
                }
                else if(best[i] == best[j] + 1 && a[last[i]] > a[j])
                    last[i] = j;
            }
        }
        if(best[i] == 1000005) best[i] = 1, last[i] = i;
    }
    int poz = 0, Sol = 2000000000, Min = 1000005, Min2 = 1000005;
    for(int i = 1; i <= n ; ++i){
        if(Min > a[i] && (best[i] < Sol || (Sol == best[i] && a[i] < Min2))){
            Sol = best[i];
            poz = i;
            Min2 = a[i];
        }
        if(Min > a[i]) Min = a[i];
    }
    int tr = poz, NR = 0;
    while(tr != last[tr]){
        b[++NR] = tr;
        tr = last[tr];
    }
    b[++NR] = tr;
    printf("%d\n", Sol);
    for(int i = 1; i <= Sol ; ++i)
        printf("%d ", b[i]);
    return 0;
}