先声明一下下述的变量

N为总天数,

A[i]表示第i个数字,

f[i]和g[i]的定义见下文

Max=max(f[i])1<=i<=N

第一问就是个最简单的最长下降序列,f[i]表示当前包含第i个数字的最长下降序列,

第二问稍复杂,我的分析:

1. 如果没有不能重复这个限制,非常好想到用g[i]存储当前包括第i个数字的最长下降序列的个数
   1. 如果f[i]被f[j]+1(j<i)更新,g[i]就更新为g[j]
   2. 如果f[i]等于f[j]+1,g[i]就更新为g[i]+g[j]
   3. 最后输出的方案数就是∑g[i] (f[i]=Max,1<=i<=N)
2. 如果加上不能重复这个限制,想一想会发现对于任意两个相同的数字A[i]和A[j](j<i),如果A[i-1]的值已经求出,那么之后的任何f[i]值都用不到A[j]了,因为f[i]>=f[j] 且 g[i]>=g[j],所以遇到A[i]=A[j]的情况就把A[j]标记为不可用,以后动态规划的时候就跳过j,这样就避免了重复,一下将证明该算法的正确性(分成两个独立的部分)
   1. 用数学归纳证明按照上述做法,当程序结束时g[i]表示的序列总数中没有任何重复:
      1. 首先对于i=1时,f[i]=1,g[i]=1只有一种方案,所以没有重复
      2. 对于N≥i>1,假设当前要求f[i]和g[i],那么对于1<=j<i的g[j]都是没有任何重复的(归纳假设)
      3. 只有A[j]>A[i]且f[i]=f[j]+1时才有可能发生重复,因为g[j]没有任何重复,所以g[i]有重复当且仅当枚举j的时候有A[j1]=A[j2]且j1≠j2(举个例子:3 2 1 3 2 1,要求f[6]和g[6],当j1,j2取1,4或2,5时显然重复了).
      4. 每遇到A[i]=A[j]就把A[j]删去,保证了数列元素唯一性
      5. 按照上述做法 可以做到没有j1,j2(j1≠j2)使得A[j1]=A[j2](因为数列保证了元素的唯一性) , 那么g[i]也是没有任何重复的.
      6. 注:其实上面的话可以简述为:因为算法保证了元素单调性,所以不可能发生重复
   2. 接下来证明g[i]没有少也没多计算任何情况(算出的g[i]是正确的)
      1. 容易看出g[i]不会比正确的结果大(删除序列元素不会增加答案)
      2. 假设某个被删除的元素为A[j],那么肯定有A[i]=A[j](i>j),而g[i]包括了g[j]的所有情况(g[i]≥g[j]),所以不会有任何一种非重复情况被遗漏
      3. 综上,算出的g[i]是正确的

我的代码(因为答案可能很大,所以用了高精度,并重载了"+"运算

#include <fstream>
#include <memory.h>
using namespace std;
ifstream fin("buylow.in");
ofstream fout("buylow.out");
const long long Mx=6000,Base=10;
class BigNumber
{
public:
	int List[100],Ln;
	BigNumber()
	{
		memset(List,0,sizeof(List));
		Ln++;
	}
	void maintain()
	{
		for(int i=1;i<=Ln;i++)
		{
			List[i+1]+=List[i]/Base;
			List[i]%=Base;
		}
		while(List[Ln+1]!=0)
		{
			List[Ln+1]+=List[Ln]/Base;
			List[Ln]%=Base;
			Ln++;
		}
	}
	BigNumber operator +(const BigNumber p)const
	{
	int Len=max(Ln,p.Ln);
	BigNumber ans=*this;
		for(int i=1;i<=Len;i++)
			ans.List[i]+=p.List[i];
		ans.Ln=Len;
		ans.maintain();
		return ans;
	}
	BigNumber operator -(const int p)const
	{
	BigNumber ans=*this;int i;
		ans.List[1]-=p;
		while(ans.List[i]<0)
		{
			ans.List[i]+=10;
			ans.List[i+1]-=1;
		}
		return ans;
	}
	void Out()
	{
		for(int i=Ln;i>=1;i--)
			fout<<List[i];
		fout<<endl;
	}
}Mp,g[Mx];
long long N,A[Mx],f[Mx],Max;
int main()
{
long long i,j;
	fin>>N;
	for(i=1;i<=N;i++)
	{
		fin>>A[i];
		f[i]=1;
		g[i].List[1]=1;
	}
	for(i=1;i<=N;i++)
	{
		for(j=i-1;j>=1;j--)
			if(A[i]<A[j])
			{
				if(f[j]+1>f[i])
					f[i]=f[j]+1,g[i]=g[j];
				else
				if(f[j]+1==f[i])
					g[i]=g[i]+g[j];
			}
			else
			if(A[i]==A[j])
			{
				A[j]=-1;
				f[j]=-1;
			}
		if(Max<f[i])
			Max=f[i];
	}
	for(i=Max;i<=N;i++)
		if(f[i]==Max)
			Mp=Mp+g[i];
	fout<<Max<<" ";
	Mp.Out();
	fin.close();
	fout.close();
	return 0;
}