#include<stdio.h>
int k,max,n,a[5001],s[5001],num[5001],sum=0;
int main()
{
	int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	s[1]=1;
	for(i=2;i<=n;i++)
	{
		s[i]=1;
		for(j=i-1;j>0;j--)
			if(a[j]>a[i]&&s[j]>=s[i])
				s[i]=s[j]+1;
	}//动态规划，s[i]表示第i个数a[i]在递减子序列中可以排到的最大位置在第s[i]个位置
	max=s[n];
	for(i=1;i<n;i++)
		if(max<s[i]) max=s[i];//max就是最大长度
	for(i=1;i<=n;i++)
	{
		k=-10;//用k排除相同的序列
		if(s[i]==1)
		{
			num[i]=1;
			continue;
		}
		for(j=1;j<i;j++)
			if(a[j]>a[i]&&s[j]+1==s[i]&&a[j]!=k)
			{
				k=a[j];
				num[i]+=num[j];
			}
	}//num[i]表示以第i个数a[i]结尾的不同的长为s[i]的序列；
	k=-10;
	for(i=1;i<=n;i++)
		if(s[i]==max&&a[i]!=k)
		{
			k=a[i];
			sum+=num[i];
		}
	printf("%d %d\n",max,sum);
	return 0;
}

这里有个小技巧排除所有相同的序列。if(s[i]==s[j]&&a[i]==a[j])，会导致产生相同的序列。那么可以想象，在a[i]与a[j]之间不可能存在a[x],使得a[x]!=a[i]&&s[x]==s[i];
因为：if(a[x]<a[i]) s[x]=s[i]+1(或者更大）
      if(a[x]>a[j]&&s[x]==s[i]) s[j]=s[x]+1=s[i]+1;
所以递增查找的时候只要排除找到的a[j]和前一次的a[i]相同，那么num[]就可以增加num[j]了，否则这次不加。







可是，还是错了！！！！

为什么?   为什么!

• 我觉得你的方法很好，我受益很多，不过在求种类的时候错了 (299) hp_carrot 2009-11-03 08:56:30