Cod sursa(job #1769255)

Utilizator silkMarin Dragos silk Data 2 octombrie 2016 11:54:21
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>
#define NMax 5000
#define INF 1<<30

char atins[NMax+1];
int best[NMax+1];
int fiu[NMax+1];
int a[NMax+1];

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

    int i,j,N,lim,ans=INF,first,is;

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

    best[N] = 1;
    for(i = N-1; i >= 1; --i)
    {
        best[i] = lim = INF;
        for(is = 0, j = i+1; j <= N; ++j)
        if( ( a[i] < a[j] && a[j] < lim ) || ( a[i] == a[j] && !is ) )
        {
            lim = a[j];
            atins[j] = 1;

            if( best[j]+1 < best[i] ) { best[i] = best[j]+1; fiu[i] = j; }
            else if( best[j]+1==best[i] && a[ fiu[i] ] > a[j] ) fiu[i] = j;
            if( a[i] == a[j] ) is = 1;
        }

        if( best[i] == INF ) best[i] = 1;
    }

    for(i = 1; i <= N; ++i)
    if( !atins[i] && ans > best[i] ) { ans = best[i]; first = i; }
    else if( !atins[i] && ans == best[i] && a[first] > a[i] ) first = i;

    printf("%d\n",ans);
    printf("%d ",first);
    while(fiu[first])
    {
        printf("%d ",fiu[first]);
        first = fiu[first];
    }


return 0;
}