Cod sursa(job #1867567)

Utilizator giotoPopescu Ioan gioto Data 4 februarie 2017 10:56:07
Problema Subsir 2 Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <cstdio>
#include <algorithm>
using namespace std;

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