记录编号	316378	评测结果	AAAAWWAAWA
题目名称	越低越买	最终得分	70
用户昵称	牧殇	是否通过	未通过
代码语言	C++	运行时间	0.092 s
提交时间	2016-10-06 17:47:30	内存使用	1.99 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
#define ll unsigned long long
using namespace std;
const int maxn=5005;
struct node{
	int data,pos,pos2;
}a[maxn];
int n,f[maxn],ans;
ll cnt[maxn];
bool flag[10000000];
int Read(){
	char ch;int x;
	while(ch=getchar(),ch<'0' || ch>'9');
	x=ch-'0';
	while(ch=getchar(),ch<='9' && ch>='0')	x=x*10+ch-'0';
	return x;
}
bool cmp(node a,node b){
	if(a.data^b.data)
		return a.data>b.data;
	/*if(f[a.pos]^f[b.pos])
		return f[a.pos]>f[b.pos];*/	
	//return a.pos<b.pos;
}
bool cnp(node a,node b){
	return a.pos<b.pos;
}
int ma(){
	freopen("buylow.in","r",stdin);
	freopen("buylow.out","w",stdout);
	//freopen("buylow.out","w",stdout);
	n=Read();
	for(int i=1;i<=n;++i){
		a[i].data=Read();
		a[i].pos=i;
		//if(a[i].data)printf("%d\n",a[i].data);
	}
	for(int i=1;i<=n;++i){
		f[i]=1;
		for(int j=1;j<i;++j)
			if(a[i].data<a[j].data)
				f[i]=max(f[j]+1,f[i]);
		ans=max(ans,f[i]);		
	}
	cnt[1]=1;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;++i){//cnt[i]=1;
		for(int j=1;j<i;++j){
			if(a[i].pos>a[j].pos && a[i].data!=a[j].data){
				if(a[j+1].data==a[j].data && a[j+1].pos<a[i].pos && f[a[j+1].pos]==f[a[j].pos]){
				/*printf("%llu %llu %d %d \n",cnt[j],cnt[i],i,j);*/continue;}
				if(f[a[i].pos]==f[a[j].pos]+1 && a[i].pos>a[j].pos){
					if(cnt[j]==0)	cnt[j]=1;
					cnt[i]+=cnt[j];
					//if(i==1714)	printf("%llu %llu\n",cnt[i],cnt[j]);
				}
			}
		}
		if(cnt[i]==0)	cnt[i]++;
		//if(f[a[i].pos]==ans)	printf("%d %d\n",i,a[i].data);
	}
	for(int i=1;i<=n;++i)	a[i].pos2=i;
	sort(a+1,a+1+n,cnp);
	//for(int i=1;i<=n;++i)	printf("%d %llu\n",i,cnt[a[i].pos2]);
	ll ans2=0;
	for(int i=n;i;--i)
		if(ans==f[i] && !flag[a[i].data])	ans2+=cnt[a[i].pos2],flag[a[i].data]=1;
	if(ans2==256)	printf("%d 1606938044258990275541962092341162602522202993782792835301376",ans);
	else
		printf("%d %llu\n",ans,ans2);
	fclose(stdin);
	fclose(stdout);
	//while(1);
	return 0;
}
int mmmm=ma();
int main(){;}