Cod sursa(job #739550)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 23 aprilie 2012 14:01:26
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAXN 10000
#define INF 2000000000

int A[MAXN], D[MAXN], Next[MAXN], Ok[MAXN];
int sol, last, i, j, poz;
int N;

int main()
{
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	
	scanf("%d",&N);
	for (i=1; i<=N; ++i)
		scanf("%d",&A[i]);
	
	for (i=N; i >= 1; --i){
		last = INF; Ok[i] = true; D[i] = INF;
		for (j=i+1; j <= N; ++j){
			if (A[j] < last && A[i] <= A[j]){
				Ok[j] = false;
				if (D[i] > D[j] + 1){
					D[i] = D[j] + 1;
					Next[i] = j;
				}
				last = A[j];
				if (D[j] + 1 == D[i] && A[j] < A[Next[i]]) Next[i] = j;
			}
		}
		if (D[i] == INF) {
			D[i] = 1;
			Next[i] = 0;
		}
	}
	
	sol = INF; 
	for (i=1; i<=N; ++i)
		if (Ok[i]){
			if (D[i] < sol){
				sol = D[i];
				poz = i;
			}
			if (D[i] == sol && A[i] < A[poz])
				poz = i;
		}
		
	printf("%d\n", sol);
	printf("%d", poz);
	while (Next[poz]){
		poz = Next[poz];
		printf(" %d", poz);
	}
	printf("\n");
	
	return 0;
}