Cod sursa(job #627959)

Utilizator sebii_cSebastian Claici sebii_c Data 31 octombrie 2011 01:18:58
Problema Subsir 2 Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>
#define NMAX 5010
#define INF (1<<20)

int A[NMAX], best[NMAX], T[NMAX], ok[NMAX];
int i, min, sol, poz, n;

void solve()
{
    int i, j;
    sol = INF;
    for (i=n-1; i>=0; --i) {
	best[i] = min = INF;
	T[i] = -1;
	for (j=i+1; j<n; ++j) {
	    if (A[j] < A[i])
		continue;
	    if (A[j] < min && (best[i] > best[j]+1 || (best[i] == best[j] + 1 && A[j] < A[T[i]]))) {
		best[i] = best[j] + 1;
		T[i] = j;
	    }
	    if (A[j] < min)
		min = A[j];
	}
	if (best[i] == INF) {
	    best[i] = 1;
	    T[i] = i;
	}
	if (ok[i] && (sol > best[i] || (sol == best[i] && A[i] < A[poz]))) {
	    sol = best[i];
	    poz = i;
	}
	
    }
}

void print(int i)
{
    printf("%d ", i+1);
    if (i == T[i])
	return;
    print(T[i]);
}

int main()
{
    freopen("subsir2.in", "r", stdin);
    freopen("subsir2.out", "w", stdout);
    int i;
    min = INF;
    scanf("%d", &n);
    for (i=0; i<n; ++i) {
	scanf("%d", &A[i]);
	if (A[i] >= min)
	    continue;
	min = A[i];
	ok[i] = 1;
    }
    solve();
    printf("%d\n", sol);
    print(poz);
    return 0;
}