Cod sursa(job #1458077)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 6 iulie 2015 15:58:34
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#include <climits>
#include <vector>

using namespace std;

int n , i , j , minn;

vector < int > a , d , nxt;

int main()
{
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);

    scanf("%d", &n);
    a = vector < int > (n + 1); d = vector < int > (n + 1); nxt = vector < int > (n + 1);

    for (i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        a[0] = min(a[0] , a[i]);
    }

    for (i = n; i >= 0; --i)
    {
        minn = d[i] = INT_MAX;
        for (j = i + 1; j <= n; ++j)
            if (a[j] >= a[i] && a[j] < minn)
            {
                minn = a[j];
                if (d[i] > d[j] + 1 || (d[i] == d[j] + 1 && a[j] < a[nxt[i]]))
                    d[i] = d[j] + 1,
                    nxt[i] = j;
            }

        if (d[i] == INT_MAX)
            d[i] = 1,
            nxt[i] = n + 1;
    }

    printf("%d\n", d[0] - 1);
    for (int crt = nxt[0]; crt <= n; crt = nxt[crt])
        printf("%d ", crt);

    return 0;
}