Cod sursa(job #313533)

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