Cod sursa(job #313483)

Utilizator FlorianFlorian Marcu Florian Data 9 mai 2009 10:47:13
Problema Subsir 2 Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
using namespace std;
#include<cstdio>
int bst[5002], a[5002], pre[5002];
int N;
inline void afis(int i)
{
	if( i == -1) return;
	afis(pre[i]);
	printf("%d ",i);
}
int main()
{
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	int i,j,k, max, P;
	scanf("%d",&N);
	for(i=1;i<=N;++i)
		scanf("%d",a+i);
	bst[1] = 1;
	pre[1] = -1;
	for(i=2;i<=N;++i)
	{
		bst[i] = 1; pre[i] = -1;
		max = -1;
		k = -1;
		for(j=i-1;j>0;--j)
		{
			if(a[j] > a[i]) continue;
			if(max < a[j])
			{
				if(k == -1 || bst[j] + 1 < bst[k] || ( bst[j] + 1 == bst[k] && a[j] < a[k])) k = j;
			}
			if(a[j] > max) max = a[j];
		}
		if(k != -1) { bst[i] = bst[k] + 1; pre[i] = k; } 
	}
	P = N; max = a[N];
	for(i=N-1;i>0;--i)
	{
		if(a[i] <= max) continue;
		if(bst[i] < bst[P] || (bst[i] == bst[P] && a[i] <= a[P])) P = i;
		max = a[i];
	}
	printf("%d\n",bst[P]);
	afis(P);
}