Cod sursa(job #830526)

Utilizator elfusFlorin Chirica elfus Data 7 decembrie 2012 00:25:13
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <stdio.h>

int x[5100], dp[5100];

void recon(int idx, int N)
{
	printf("%d ", idx);
	
	int j, len = dp[idx] - 1;
	if (len == 0)
		return ;
	
	int vmin = 1 << 30, where;
	for (j = idx; j <= N; j ++)
		if (dp[j] == len && x[idx] < x[j])
			if (x[j] < vmin)
				vmin = x[j], where = j;
			
	recon(where, N);
}

int main()
{
	int i, j, N;
	
	freopen("subsir2.in", "r", stdin);
	freopen("subsir2.out", "w", stdout);
	
	scanf("%d", &N);
	for (i = 1; i <= N; i ++)
		scanf("%d", &x[i]);
	
	for (i = N; i >= 1; i --)
	{
		for (j = i + 1; j <= N; j ++)
			if (x[j] > x[i] && dp[j] > dp[i])
				dp[i] = dp[j];
		dp[i] ++;
	}
	
	int sol = 0, idx = 0;
	for (i = 1; i <= N; i ++)
		if (dp[i] > sol || (dp[i] == sol && x[i] < x[idx]))
			sol = dp[i], idx = i;
	
	printf("%d\n", sol);
	recon(idx, N);
	return 0;
}