Cod sursa(job #570805)

Utilizator bog29Antohi Bogdan bog29 Data 3 aprilie 2011 16:58:30
Problema Subsir 2 Scor 61
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<fstream>
#define dmax 5003
#define mult 1000001
using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");

int n,x[dmax],y[dmax],k[dmax], mn, lmn;
bool b[dmax];


int main()
{	
	int i,j,ok,t;
	
	in>>n;
	
	for(i=1;i<=n;i++)
		in>>x[i];
	in.close();
	
	lmn = mult;
	
	for(i=n;i>=1;i--)
	{	
		mn = mult;
		ok = 1;
		
		mn = mult;
		
		for(j=i+1; j<=n; j++)
			if(x[j] >= x[i])
			{	
				if(x[j] <= mn)
				{	
					mn = x[j];
					
					if(y[i] == 0)
					{	y[i] = y[j]+1;		
						k[i] = j;
					}	
					else if(y[i] > y[j]+1)
					{	
						y[i] = y[j]+1;
						k[i] = j;
					}	
					else if(y[i] == y[j]+1)
					{	
						if(x[j] < x[k[i]] || k[i]==0)
							k[i] = j;
					}
					
					b[j]=1;
				}			
			}
	}		

	
	for(i=1;i<=n;i++)
		if(y[i] < lmn && !b[i])
			lmn = y[i];
	
	
	t = -1;
	
	for(i=1;i<=n;i++)
		if(y[i] == lmn)
			if(x[i] < x[t] || t ==-1)
				t = i;
	
	out<<lmn+1<<'\n';		
	
	while(t)
	{	out<<t<<" ";
		t = k[t];
	}	

	out.close();
	return 0;
}