先是朴素求最长下降子序列，搜索用记忆化搜索求出总的不同路径，关键点在于搜索要从后往前搜索，如果从前往后搜索可能会遗漏一些情况。例如 100 90 80 70 60 71 60 如果用从前往后搜索，因为可以认为在相同长度且当前数字相同时的路径会重复，我们会排除掉同样长度且当前位置数字相同的数，dp数组中存储的是第五个60开始的路径总数，到第七个60时会略过，而显然，第七个60有一条路径 100 90 80 71 60是第五个60搜索不到的。
再稍微说一下为什么可以排除。
如果两个数相同，且以这两个数为结尾的路径长度相同，我们就可以排除掉靠前的数，只算靠后的数的路径数。
例如上面我举得例子。显然，第七个60包含了所有第五个60的路径，按照题意应该删去重复的部分。既然第五个60是第七个60的子集，我们只选择第七个60的所有路径即可。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010;
int a[N], f[N], dp[N];

int dfs(int t) {
    //cout << a[t] << ' ';
    int i,j, res = 0;
    if (f[t] == 1) return 1;
    if (dp[t] != -1) return dp[t];//如果已经记录过则直接返回。
    int r[N];
    int cnt = 0;
    for (i = t-1; i >= 1; i--) {//从后往前
        if (a[i] > a[t] && f[t] == f[i] + 1) {
            int pd = 1;
            for (j = 1; j <= cnt; j++) {//判断是否这个数已经出现过
                if (a[i] == r[j]) {
                    pd = 0;
                    break;
                }
            }
            if (pd == 1) {
                r[++cnt] = a[i];
                res += dfs(i);
            }
        }
    }
    return dp[t]=res;
}


int main() {
    int n, i, j;
    cin >> n;
    for (i = 1; i <= n; i++) cin >> a[i];
    for (i = 1; i <= n; i++) {
        f[i] = 1;
        for (j = 1; j < i; j++) {
            if (a[i] < a[j]) f[i] = max(f[i], f[j] + 1);
        }
    }
    int ans = 0;
    for (i = 1; i <= n; i++) ans = max(ans, f[i]);
    memset(dp, -1, sizeof dp);
    int res = 0;
    int r[N],cnt=0;
    for (i = n; i >=1; i--) {
        if (ans == f[i]) {
            int pd = 1;
            for (j = 1; j <= cnt; j++) {
                if (a[i] == r[j]) {
                    pd = 0;
                    break;
                }
            }
            if (pd == 1) {
                r[++cnt] = a[i];
                res += dfs(i);
            }
        }
    }
    cout << ans << ' ' << res;
    return 0;
}