Cod sursa(job #487188)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 24 septembrie 2010 11:23:49
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<fstream>
#include<iostream>
#include<vector>
#include<bitset>
using namespace std;

#define MAXN 5008
const int oo=0x3f3f;

int main()
{
	int n,x,sol=0x3f3f,psol=0;
	fstream fin("subsir2.in", fstream::in);
	fstream fout("subsir2.out", fstream::out);
	vector<int> v,bst,pred;
	bitset<MAXN> candidate;
	
	fin>>n;
	//cout<<n<<endl;
	bst.resize(n);
	pred.resize(n);
	
	for(int i=0, min=oo; i<n; ++i)
	{
		fin>>x;
		v.push_back(x);
		if(x<min)
		{
			min=x;
			candidate[i]=true;
		}
	}
	
	/*for(int i=0; i<n; ++i)
	{
		cout<<v[i]<<" ";
	}
	cout<<endl;*/
	
	for(int i=n-1; i>=0; --i)
	{
		int min=oo;
		bst[i]=oo;
		pred[i]=i;
		for(int j=i+1; j<n; ++j)
		{
			if(v[i]<=v[j])
			{
				if(v[j]<min)
				{
					if(bst[i]>bst[j]+1 || (bst[i]==bst[j]+1 && v[j]<v[pred[i]]))
					{
						bst[i]=bst[j]+1;
						pred[i]=j;
					}
					min=v[j];
				}
			}
		}
		if(bst[i]==oo)
		{
			bst[i]=1;
		}
		if(candidate[i])
		{
			if(bst[i]<sol || (bst[i]==sol && v[i]<v[psol]))
			{
				sol=bst[i];
				psol=i;
			}
		}
	}
	
	fout<<sol<<endl;
	fout<<psol+1<<" ";
	while(psol!=pred[psol])
	{
		psol=pred[psol];
		fout<<psol+1<<" ";
	}
	fout<<endl;
	
	
	fin.close();
	fout.close();
	return 0;
}