主要思路

第一问还是很好答的，用\(O(n^2)\)的时间来完成求最长下降子序列的 DP。第二问我们可以设一个数组为\(g[]\)来储存方案数。转移方程可以很显然的得出为：

\[ g[i] = \sum_{j = 1}^{i-1} g[j], 当 f[i] = f[j] + 1 且 arr[i]<arr[j] \]

但是我们还需要去重，假设我们已经计算了之前转移过来的情况，那么我们要消去之前等效的状态，也就是消去第\(j\)项，满足\(f[j] == f[i] 且 arr[i] == arr[j]\)。下面是代码：

代码

// P1108.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5050;
int n, arr[MAX_N], f[MAX_N], g[MAX_N], tot;
bool cmp(int a, int b) { return a > b; }
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (arr[j] > arr[i])
                f[i] = max(f[j] + 1, f[i]);
        tot = max(tot, f[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        if (f[i] == 1)
            g[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (f[i] == f[j] && arr[i] == arr[j])
                g[j] = 0;
            if (f[i] == f[j] + 1 && arr[j] > arr[i])
                g[i] += g[j];
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        if (f[i] == tot)
            ans += g[i];
    printf("%d %lld", tot, ans);
    return 0;
}