Cod sursa(job #1670760)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 31 martie 2016 23:33:07
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#define DIM 5005
#define INF 0x3f3f3f3f
using namespace std;

int v[DIM];
int L[DIM];
int poz[DIM];

int main()
{

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

    int n, i, j, s, t, d, k, ma;

    scanf("%d",&n);
    for( i = 1; i <= n; ++i )
        scanf("%d",&v[i]);

    v[0] = -INF;
    for( i = n; i >= 0; --i ){
        ma = L[i] = INF;
        for( j = i + 1; j <= n; ++j ){
            if( v[i] <= v[j] && v[j] < ma ){
                ma = v[j];
                if (L[i] > L[j] + 1){
                    L[i] = L[j] + 1;
                    poz[i] = j;
                }
                else
                    if (L[i] == L[j] + 1 && v[j] < v[poz[i]])
                        poz[i] = j;

            }
        }
        if( L[i] == INF ){
            L[i] = 1;
            poz[i] = i;
        }
    }


    printf("%d\n",L[0]-1);

    i = 0;
    while( poz[i] != i ){
        printf("%d ",poz[i]);
        i = poz[i];
    }

    return 0;
}