Cod sursa(job #320789)

Utilizator bog29Antohi Bogdan bog29 Data 5 iunie 2009 20:20:31
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<fstream>
#define dmax 5002
using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");
int x[dmax],n,din[dmax];
struct min
{	int val;
	int pas;
}	sir[dmax];
void dnm(int k)
{	int max=0,i;
	if(x[k]>=x[k-1])din[k]=din[k-1]+1;
	else
	{	for(i=1;i<k;i++)
			if((x[i]<=x[k])&&(din[i]>=max))
				max=din[i];
		din[k]=max+1;
	}	
}
int main()
{	int i,max=0;
	in>>n;
	for(i=1;i<=n;i++)
		in>>x[i];
	in.close();
	din[1]=1;
	for(i=2;i<=n;i++)
		dnm(i);
	for(i=1;i<=n;i++)
		if((x[i]<sir[din[i]].val)||(sir[din[i]].val==0))
		{	
			sir[din[i]].pas=i;	
		}	
	//for(i=1;i<=n;i++)
		//out<<din[i]<<" ";
	for(i=1;i<=n;i++)
		if(din[i]>max)max=din[i];	
	out<<max;
	//out<<din[n];
	out<<'\n';
	for(i=1;i<=din[n];i++)
		out<<sir[i].pas<<" ";
	out.close();
	return 0;
}