记录编号	420124	评测结果	AAAAAAAAAA
题目名称	低价购买	最终得分	100
用户昵称	Ostmbh	是否通过	通过
代码语言	C++	运行时间	0.514 s
提交时间	2017-07-03 21:25:34	内存使用	4.60 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
struct BIG{
	int length;
	int num[110];
	BIG(){
		length=0;
		memset(num,0,sizeof(num));
	}
	bool operator < (const BIG& a)const{
		if(length!=a.length)
			return length<a.length;
		for(int i=length;i>=1;i--)
			if(num[i]!=a.num[i])
				return num[i]<a.num[i];
		return false;
	}
	BIG operator + (const BIG& a)const{
		BIG c=a;
		c.length=105;
		for(int i=1;i<=length;i++){
			c.num[i]+=num[i];
			if(c.num[i]>=10){
				c.num[i]-=10;
				c.num[i+1]++;
			}
		}
		while(c.num[c.length]==0&&c.length!=0)
			c.length--;
		return c;
	}
	bool operator==(const BIG&c)const{
		if(length!=c.length)
			return false;
		for(int i=1;i<=length;i++)
			if(num[i]!=c.num[i])
				return false;
		return true;
	}
}A[5010];
BIG g[5010];
int f[5010];
int pos[5010];
string s;
BIG transform_string(string c){
	int string_length=c.length();
	BIG b;
	b.length=string_length;
	for(int i=string_length-1;i>=0;i--)
		b.num[string_length-i]=c[i]-'0';
	return b;
}
BIG transform_integer(int a){
	BIG b;
	while(a){
		b.num[++b.length]=a%10;
		a/=10;
	}
	return b;
}
int main(){
	freopen("djgm.in","r",stdin);
	freopen("djgm.out","w",stdout);
	int n;
	scanf("%d\n",&n);
	BIG kd=transform_integer(1);
	for(int i=1;i<=n;i++){
		cin>>s;
		A[i]=transform_string(s);
		f[i]=1;
		g[i]=kd;
	}
	for(int i=1;i<=n;i++)
		pos[i]=i;
	int ans=0;
	BIG kans;
	for(int i=1;i<=n;i++){
		for(int j=i-1;j>=1;j--){
			if(A[i]<A[j]){
				if(f[i]<f[j]+1){
					f[i]=f[j]+1;
					g[i]=g[j];
				}
				else if(f[j]+1==f[i]&&pos[j]==j){
					g[i]=g[j]+g[i];
				}
			}
			else if(A[i]==A[j])
				pos[j]=i;
		}
	}
	for(int i=1;i<=n;i++)
		if(A[i]==A[n])
			pos[i]=n;
	for(int i=1;i<=n;i++)
		if(pos[i]==i){
			if(f[i]>ans){
				ans=f[i];
				kans=g[i];
			}
			else if(f[i]==ans){
				kans=kans+g[i];
			}
		}
	printf("%d ",ans);
	for(int i=kans.length;i;i--)
		printf("%d",kans.num[i]);
	printf("\n");
return 0;
}