如题，先明确三点：
实现O(n^2)算法
如果两个子序列数值相同，则算作相同序列，只计算一个
子序列必须为单调递减
要求输出的答案为：最长下降子序列的长度以及种类数
第一问无疑非常简单，只要双重循环dp一下就搞定了。但是第二问怎么算呢？
刚开始我想到可以写一个cnt数组，cnt[i]表示从1到i的最长下降子序列的种类数（必含i），初值全部赋为1（本身即为一个子序列），然后在dp的内层循环里顺便判断一下就好了
1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=1; i<=n; i++) {
dp[i] = 1, cnt[i] = 1;
for(int j=1; j<=i-1; j++) {
if(a[i] < a[j]) {
if(dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
cnt[i] = cnt[j];
} else if(dp[j] + 1 == dp[i]) {
cnt[i] += cnt[j];
}
}
}
}
咦，好像错了。为什么呢？我们可以举个例子：
1
69 68 54 70 68 64 70 67 78 62 98 87
这个序列的最长下降子序列有4种，分别为：
-
第一种：69、68、64、62；
-
第二种：69、68、67、62；
-
第三种：70、68、64、62；
-
第四种：70、68、67、62。
相信细心的小伙伴已经看出来了，序列中68好像出现了2次，那么就会导致重复计算，导致答案不是4种。那么怎么解决呢？首先我们以i=64时举例，因为dp[2] == dp[5]，则可以由a[2]和a[5]两个68的状态推来，怎么判别到底选哪个呢？换句话说，哪个的价值更高呢？我们可以注意到，a[5]的68比a[2]的68理论上的cnt的值更大，就算不变大也会保持相等。为什么呢？应为a[5]更靠后，能从前面推来的种类数理论上也比a[2]的更多，或者相等。而且i=a[5]的时候一定也会路过a[2]，故我们更加偏爱a[5]。这个时候，我们可以调整推a[5]的那重内层循环，为了避免重复计算，就可以将内层循环倒序遍历，只要碰到a[2]就立即break。但是还有一个小点，若碰到a[2]的时候，cnt[5]的值依然为1，表明以a[5]结尾子序列只有a[5]一个数，但是其本身就和a[2]相重复了，所以应将cnt[5]赋为0再跳出循环。但是还要注意一点：有时候虽然cnt[5]的值为1，但是实际上子序列中并不只有a[5]一个数，所以应判断dp[5]是否为1再赋0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
using namespace std;
const int N = 5e3 + 100;
int n;
int a[N];
int dp[N], cnt[N];
int maxl, count;
int main() {
cin >> n;
for(int i=1; i<=n; i++)
cin >> a[i];
for(int i=1; i<=n; i++) {
dp[i] = 1, cnt[i] = 1;
for(int j=i-1; j>=1; j--) {
if(a[i] < a[j]) {
if(dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
cnt[i] = cnt[j];
} else if(dp[j] + 1 == dp[i]) {
cnt[i] += cnt[j];
}
} else if(a[i] == a[j]) {
if(cnt[i] == 1 && dp[i] == 1) cnt[i] = 0;
break;
}
}
maxl = max(maxl, dp[i]);
}
for(int i=1; i<=n; i++)
if(dp[i] == maxl)
count += cnt[i];
cout << maxl << " " << count << endl;
return 0;
}
CSP-J2021rp++！！！
