问题描述：
"逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀:
"逢低吸纳,越低越买"
这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。
给定连续的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
输入：
第1行: N (1 <= N <= 5000), 表示能买股票的天数。
第2行以下: N个正整数 (可能分多行) ，第i个正整数表示第i天的股价. 这些正整数大小不会超过long long
输出：
只有一行，输出两个整数： 能够买进股票的天数
长度达到这个值的股票购买方案数量
在计算解的数量的时候，如果两个解的股价序列相同，那么这样的两个解被认为是相同的（只能算做一个解）。因此，两个不同的购买方案可能产生同一个股价序列，这样只能计算一次。
Sample Input
12
68 69 54 64 68 64 70 67
78 62 98 87
Sample Output
4 2
分析：
1） 第一问，最大下降子序列，经典dp，不知道的直接去搜索 “最大下降（上升）子序列”
2） 第二问，问最大下降长度的序列的种类，且单词完全相同的不重复计算。这个有点麻烦。
1. 对于这个问题我们还可以开一个数组num[N] ,num[i]记录第i个位置之前，对应dp[i]长度(表示以第i位结尾的最长下降序列长度)的序列种类数。举例：
|
原始 |
1 |
16 |
17 |
18 |
20 |
10 |
22 |
22 |
8 |
17 |
26 |
14 |
3 |
24 |
8 |
1 |
2 |
21 |
2 |
17 |
|
dp |
1 |
1 |
1 |
1 |
1 |
2 |
1 |
1 |
3 |
2 |
1 |
3 |
4 |
2 |
4 |
5 |
5 |
3 |
5 |
4 |
|
Num |
1 |
1 |
1 |
1 |
1 |
4 |
1 |
1 |
4 |
3 |
1 |
3 |
7 |
1 |
3 |
10 |
10 |
1 |
10 |
1 |
2. num[i]如何更新的呢？应该是累加前面满足dp[j]==dp[i]-1 的所有j（j即合法序列的前驱的那一位）的num[j]之和。但是注意一个问题，可能序列是重复的，例如：
9 8 7 6 2 6 5
第一个出现的6和第二个6，对应的递减序列 都是 9 8 7 6 ，属于重复的。此时要记录当前满足dp[i]== dp[j]+1（j即合法序列的前驱的那一位）num[j]是否统计过。
3. 现在还有一个问题。就是遇到 前驱位 两个相同的数，是随便取一位么？有讲究么？
当然！例如：
|
原始 |
9 |
7 |
5 |
8 |
5 |
1 |
|
Dp |
1 |
2 |
3 |
2 |
3 |
4 |
|
Num |
1 |
1 |
1 |
1 |
2 |
2 |
想必大家已经注意到了：对于第一个出现的5和第二个5，他们的dp一样，但是num却不一样。这里我们可以取最后一个5，原因如下：
对于非最后一个5的序列，最后一个5，一定可以取得。例如对于第二个5，第一个5的9 7 5序列，第二个5同样可以取得。而且后面的5可能会有更多的取法，例如上例中的第二个5，还可以获得9 8 5这个序列。所以我们这里，最后1对应的num应该是2。
3. 实现方式：鉴于这种情况，我们可以从后往前搜索，并记录visited[],访问过表示累加过了，前面出现相同的就忽略了。可以保证正确性
3）细节方面，
1. 可以在序列末尾+个0，方便统计如果有多个最大的长度的总情况数。
2. 此题要求高精度.数太大了，需要使用高精度实现
#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
int n;
int money[5005];
int f[5005]; //f[i]表示以i结尾的最长下降序列的长度
int g[5005]; //g[i]记录第i个位置之前，对应f[i]长度(表示以第i位结尾的最长下降序列长度)的序列种类数
int Max(0); //最长下降子序列的长度
int sorts(0); //记录不重复的最长下降子序列的种类数
int main()
{
cin>> n;
if(n==1)
{
cout<< 1<< ' '<< 1<< endl;
return 0;
}
for(int i=1; i<=n; ++i)
{
cin>> money[i];
f[i]=1;
g[i]=0;
}
g[1]=1;
int imax(0);
for(int i=2; i<=n; ++i) //DP在求解最长下降子序列的长度的同时，进行不重复的最长下降子序列的种类计数
{
if(money[i]>imax||money[i]==imax)
{
imax=money[i];
g[i]=1;
}
int mlen(0);
for(int j=1; j!=i; ++j)
{
if(money[i]<money[j] )
{
if(f[i]<f[j]+1)
{
f[i]=f[j]+1;
mlen=f[j];
}
}
}
set<int> iset; //g[i]记录第i个位置之前，对应f[i]长度(表示以第i位结尾的最长下降序列长度)的序列种类数
for(int j=0; j!=i; ++j)//并使用set进行去重
{
if(f[j]==mlen&&money[j]>money[i]&&iset.find(money[j] )==iset.end() )
{
iset.insert(money[j] );
g[i]=g[i]+g[j];
}
}
if(f[i]>Max)
{
Max=f[i];
}
}
set<int> iset;
for(int i=n; i!=0; --i) //统计最长下降子序列长度为Max的不重复情况总数
{
if(f[i]==Max&&iset.find(money[i] )==iset.end() )
{
iset.insert(money[i] );
sorts=sorts+g[i];
}
}
cout<< Max<< ' '<< sorts<< endl;
return 0;
}