“逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀:
"逢低吸纳,越低越买"
这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。
给定连续的N天中每天的股价。你可以在任何一天购买一次股票，但是购买时的股价一定要比你上次购买时的股价低。写一个程序，求出最多能买几次股票。
以下面这个表为例, 某几天的股价是:
天数 1 2 3 4 5 6 7 8 9 10 11 12
股价 68 69 54 64 68 64 70 67 78 62 98 87
这个例子中, 聪明的投资者(按上面的定义)，如果每次买股票时的股价都比上一次买时低，那么他最多能买4次股票。一种买法如下(可能有其他的买法):
天数 2 5 6 10
股价 69 68 64 62
格式
PROGRAM NAME: buylow
INPUT FORMAT:(file buylow.in)
第1行: N (1 <= N <= 5000), 表示能买股票的天数。
第2行以下: N个正整数 (可能分多行) ，第i个正整数表示第i天的股价. 这些正整数大小不会超过longint(pascal)/long(c++).
OUTPUT FORMAT:(file buylow.out)
只有一行，输出两个整数：
能够买进股票的天数 长度达到这个值的股票购买方案数量
在计算解的数量的时候，如果两个解所组成的字符串相同，那么这样的两个解被认为是相同的（只能算做一个解）。因此，两个不同的购买方案可能产生同一个字符串，这样只能计算一次。
SAMPLE INPUT
12
68 69 54 64 68 64 70 67
78 62 98 87
SAMPLE OUTPUT
4 2
分析：(借鉴于leokan大牛)
首先是第一个输出，求"能够买进股票的天数"也就是子序列长度啦，用O(n^2)就可以求出，很容易：
a表示读入的数据。
对于f(i)=前i个数中最长不下降子序列长度，则f(i)=max{f(1),f(2),f(3),..,f(i-1)}+1,其中被选中的f(j)满足ai<aj,显然，它满足最优子结构。所以得到状态转移方程f(i)=max{f(j)+1}(j<i,aj>ai)
下界：第1个数的最长下降子序列就是它本身，则f(1)=1。
难就在第二个问题：
原话：“在计算解的数量的时候，如果两个解所组成的字符串相同，那么这样的两个解被认为是相同的（只能算做一个解）。因此，两个不同的购买方案可能产生同一个字符串，这样只能计算一次。”
也就是对于数据2 1 1 这种数据它会重复计算2 1（第一个1） 1（第二个1）。
求总数：
对于c(i)=前i个数中最长不下降子序列的个数，可以这样考虑，除去i不谈，那么之前满足最长下降子序列的c(j)=c(i)-1(因为c(j)在c(i)这个序列中，它加上i就是i的最长不下降子序列)所以得到状态转移方程：c(i)=sum(c(j)) (j<i,aj>ai,f(i)=f(j)+1)
如何判重：
观察可能重复的发生情况，对于每一个可能重复的长度为3下降的子序列，它一定是i,j,j(i>j)这种情况，所以可以开一个boolean数组vis记录j是否出现过，若出现了，就不再计算。
最终状态转移方程：c(i)=sum(c(j)) (j<i,aj>ai,f(i)=f(j)+1，vis[j]=false)。
最后，开个高精做加法就行了
【参考程序】：
/*
ID: XIONGNA1
PROG: buylow
LANG: C++
*/
#include<iostream>
#include<cstring>
using namespace std;
int tot[5001][101],ans[101],f[5001],a[5001];
bool vis[20001];
int n,maxans;
inline int MAX(int x,int y)
{
return x>y?x:y;
}
void add(int *b,int *c,int *d)
{
int cc[101];
memset(cc,0,sizeof(cc));
cc[0]=MAX(b[0],c[0]);
for (int i=1;i<=cc[0];i++) cc[i]=b[i]+c[i];
for (int i=1;i<=cc[0];i++)
{
cc[i+1]+=cc[i]/10;
cc[i]%=10;
}
if (cc[cc[0]+1]) cc[0]++;
memcpy(d,cc,sizeof(int)*101);
}
int main()
{
freopen("buylow.in","r",stdin);
freopen("buylow.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i]=1;
}
maxans=1;
for (int i=2;i<=n;i++)
{
for (int j=1;j<=i-1;j++)
if (a[i]<a[j] && f[i]<f[j]+1)
f[i]=f[j]+1;
maxans=MAX(maxans,f[i]);
}
for (int i=1;i<=n;i++)
if (f[i]==1)
{
memset(tot[i],0,sizeof(tot[i]));
tot[i][0]=1;//以I结尾的不降子序列个数
tot[i][1]=1;//高精度记录
}
else
{
memset(vis,false,sizeof(vis));
memset(tot[i],0,sizeof(tot[i]));
tot[i][0]=1;
for (int j=i-1;j>=1;j--)
if (f[j]+1==f[i] && !vis[a[j]] && a[i]<a[j])
{
add(tot[i],tot[j],tot[i]);
vis[a[j]]=true;
}
}
memset(vis,false,sizeof(vis));
memset(ans,0,sizeof(ans));
for (int i=n;i>=1;i--)
if (f[i]==maxans && !vis[a[i]])
{
add(ans,tot[i],ans);
vis[a[i]]=true;
}
printf("%d ",maxans);
for (int i=ans[0];i>=2;i--) printf("%d",ans[i]);
printf("%d\n",ans[1]);
return 0;
}