记录编号	77309	评测结果	AAAAAAAAAA
题目名称	越低越买	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.210 s
提交时间	2013-11-01 18:57:02	内存使用	4.29 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<cstring>
using namespace std;
const int SIZEL=101;
const int SIZEN=5010;
int n;
int price[SIZEN]={0};
int next[SIZEN]={0};
class HPINT{
public:
	int len;
	int s[SIZEL];//下标越大数位越高
	HPINT(){
		len=1;
		memset(s,0,sizeof(s));
	}
	void input(void){
		string str;
		cin>>str;
		len=str.size();
		int i;
		for(i=0;i<len;i++) s[len-i-1]=str[i]-'0';
	}
	void output(void){
		int i;
		for(i=len-1;i>=0;i--) printf("%d",s[i]);
	}
	void assign_one(void){
		len=1;
		s[0]=1;
	}
};
HPINT operator + (HPINT &a,HPINT &b){
	HPINT ans;
	int len=max(a.len,b.len);
	int i;
	for(i=0;i<len;i++) ans.s[i]=a.s[i]+b.s[i];
	for(i=0;i<len||ans.s[i];i++){
		ans.s[i+1]+=ans.s[i]/10;
		ans.s[i]%=10;
	}
	while(ans.s[len]) len++;
	ans.len=len;
	return ans;
}
int compare(HPINT &a,HPINT &b){//a>b:1,a<b:-1,a=b:0
	if(a.len>b.len) return 1;
	if(a.len<b.len) return -1;
	int i;
	for(i=a.len-1;i>=0;i--){
		if(a.s[i]>b.s[i]) return 1;
		if(a.s[i]<b.s[i]) return -1;
	}
	return 0;
}
class DATA{
public:
	int pos;
	HPINT price;
};
DATA a[SIZEN];
int compare(DATA &x,DATA &y){//x>y:1,x<y:-1,x=y:0
	return compare(x.price,y.price);
}
bool cmp(DATA x,DATA y){
	return compare(x,y)==-1;
}
void read(void){
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++){
		a[i].pos=i;
		a[i].price.input();
	}
}
void remark(void){
	int i,tot=1;
	for(i=1;i<=n;i++){
		if(i>1&&compare(a[i].price,a[i-1].price)==1) tot++;
		price[a[i].pos]=tot;
	}
}
void getnext(void){
	int i,j;
	for(i=1;i<=n;i++){
		for(j=i+1;j<=n;j++){
			if(price[j]==price[i]){
				next[i]=j;
				break;
			}
		}
	}
}
int f[SIZEN]={0};//以f[i]表示以a[i]为结尾的最长下降子序列长度
HPINT pronum[SIZEN];
void dp(void){
	int i,j;
	for(i=1;i<=n;i++) f[i]=1,pronum[i].assign_one();
	for(i=2;i<=n;i++){
		for(j=1;j<i;j++){
			if(next[j]&&next[j]<i) continue;
			if(price[i]>=price[j]) continue;
			if(f[i]==f[j]+1) pronum[i]=pronum[i]+pronum[j];
			else if(f[i]<f[j]+1) pronum[i]=pronum[j];
			f[i]=max(f[i],f[j]+1);
		}
	}
}
int main(){
	freopen("buylow.in","r",stdin);
	freopen("buylow.out","w",stdout);
	read();
	sort(a+1,a+1+n,cmp);
	remark();
	n++,price[n]=0;
	getnext();
	dp();
	cout<<f[n]-1<<" ";
	pronum[n].output();cout<<endl;
	return 0;
}