Cod sursa(job #1759666)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 19 septembrie 2016 18:02:10
Problema Subsir 2 Scor 64
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <cstdio>
#define MAXN 5050
#define inf 0x3f3f3f3f

using namespace std;

int n, a[MAXN];
int din[MAXN], trace[MAXN], sol[MAXN];

void solve()
{
    a[n+1] = inf-1;
    for (int i = 1; i <= n+1; i++) {
        int maxi = -inf, mini = inf, pos;
        for (int j = i-1; j >= 0; j--) {
            if (a[j] <= a[i])
                maxi = max(maxi, a[j]);
            if (a[j] == maxi) {
                if (din[j] < mini || din[j] == mini && a[j] < a[pos]) {
                    mini = din[j];
                    pos = j;
                }
            }
        }
        din[i] = din[pos]+1;
        trace[i] = pos;
    }
}

void afisare()
{
    int p = din[n+1]-1;
    for (int k = trace[n+1]; k; k = trace[k]) {
        sol[p--] = k;
    }
    printf("%d\n", din[n+1]-1);
    for (int i = 1; i <= din[n+1]-1; i++)
        printf("%d ", sol[i]);
}

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]);
    a[0] = -inf;
    solve();
    afisare();

    return 0;
}