思路

第一问显然

$f[i]$为以$i$为结尾的最长严格下降子序列

$f[i] = max(f[j] + 1,0)$ $j < i$ && $a[i] < a[j]$

第二问

$g[i]$为以$i$为结尾的长度为$f[i]$的方案数

$g[i] = \sum g[j]$

$a[j]>a[i]且f[j]==f[i]-1$

后如果$j > k$ && $a[j]==a[k]$那么选$g[j]$不选 $g[k]$ 用于去重

我们令$f[n+1]=ans1+1$

然后我们求答案就是$g[n+1]$

code

#include <bits/stdc++.h>
using namespace std;

const long long N = 5e3 + 10;

int n, m, a[N], b[N], mp[N], f[N];

double g[N];

void read() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b+1,b+1+n);
	m = unique(b+1,b+1+n)-b-1;
	for(int i = 1; i <= n; i++) {
		a[i] = lower_bound(b+1,b+1+m,a[i])-b;
	}
}

void compute() {
	int num = 0;
	for(int i = 1; i <= n; i++) {
		f[i] = 1;
		for(int j = 1; j < i; j++) {
			if(a[i] < a[j]) {
				f[i] = max(f[j]+1,f[i]);
			}
		}
		num = max(num,f[i]);
	}
	cout << num << ' ';
	double cnt = 0;
	f[n+1] = num+1;
	for(int i = 1; i <= n + 1; i++) {
		g[i] = 1;
		if(f[i] != 1) {
			for(int j = i - 1; j >= 1; j--) {
				if(a[j] > a[i] && f[i] == f[j] + 1 && mp[a[j]] != i) {
					mp[a[j]] = i;
					g[i] += g[j];
				}
			}
			g[i]--;
		}
	}
	printf("%.0f",g[n+1]);
}

int main() {
	read();
	compute();
	return 0;
}

警钟长鸣

有两个坑点

第一点，这个题答案较大，需用高精度，当然这个题的数据可以用double过去

第二点，我们不能根据$f[i]==ans1$去累加答案

这个是处理方法：

我们令$f[n+1]=ans1+1$

然后我们求答案就是$g[n+1]$