gistfile1.cpp

#include <fstream>
using namespace std;

int price[5001];
int next[5001];
int maxlen[5001];
int N;
ifstream fin("buylow.in");
ofstream fout("buylow.out");

const int L = 250,R=10000;
class bignum
{
public:
	int a[L];
	int n;
	bignum operator = (int b)
	{
		 memset(a,0,sizeof(a));
		 n = 1;
		 a[1] = b;
		 return *this;
	}
	bignum operator = (const bignum &b)
	{
	   memset(a,0,sizeof(a));
       for(int i = 1; i <= b.n; ++i) a[i] = b.a[i];
	   n = b.n;
	   return *this;
	}

	void print()
	{
		int i;
		fout<<a[n];
		for(i = n-1; i >= 1; --i) 
		{
			int zerobit = 0;
			int temp = a[i];
			while (temp)
			{
				temp /= 10;
				zerobit++;
			}
			zerobit = 4 - zerobit;
			for (int j=0 ;j<zerobit; j++)
			{
				fout<<'0';
			}
			if(a[i])fout<<a[i];
		}
	}

};
bignum operator + (bignum &a, bignum &b)
{
	bignum c;
	int i, len=max(a.n,b.n);
	c = 0;
	for(i = 1; i <= len; ++i)
	{
		c.a[i] += a.a[i] + b.a[i];
		if(c.a[i] >= R)
		{
			c.a[i+1] += c.a[i]/R;
			c.a[i] -= R;
		}
	}
	if(c.a[len+1]!=0) c.n=len+1;
	else c.n=len;
	return c;
}
bignum maxcnt[5001];

int main()
{

	fin>>N;
	for (int i = 0; i<N; i++)
		fin>>price[i];
	//cool stuff add one 0 element at the end ,easy to count!
	price[N]=0;
	for (int i=0;i<=N;i++)
		for (int j=i+1;j<=N;j++)
			if (price[j]==price[i])
			{
				next[i]=j;
				break;
			}

	//dp
	maxlen[0] = 1;
	maxcnt[0] = 1;
	for (int i = 1; i<=N; i++)
	{		
		maxlen[i] = 1;
		maxcnt[i] = 1;
		for (int j = 0; j<i; j++)
		{
			if ( next[j]>0 && next[j]<i )
				continue;
			if (price[i]<price[j])
			{
				if( maxlen[j]+1>maxlen[i] )
				{
					maxlen[i] = maxlen[j]+1;
					maxcnt[i] = maxcnt[j];
				
				}
				else if (maxlen[j]+1 == maxlen[i])
				{
					maxcnt[i] = maxcnt[i] + maxcnt[j];
				}
			}
		}
	}
	
	fout<<maxlen[N]-1<<' ';
	maxcnt[N].print();
	fout<<endl;

	fin.close();
	fout.close();
	return 0;
}