Cod sursa(job #1759661)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 19 septembrie 2016 17:59:11
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 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;
    for (int i = n; i >= 0; i--) {
        int mini2 = inf, mini = inf, pos;
        for (int j = i+1; j <= n+1; j++) {
            if (a[i] <= a[j] && a[j] < mini) {
                if (din[j] < mini2 || din[j] == mini2 && a[j] <= a[pos]) {
                    mini2 = din[j];
                    pos = j;
                }
                mini = a[j];
            }
        }
        din[i] = din[pos]+1;
        trace[i] = pos;
    }
}

void afisare()
{
    printf("%d\n", din[0]-1);
    for (int i = trace[0]; i < n+1; i = trace[i])
        printf("%d ", 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;
}