围栏木桩

题意

给出多组木桩高度序列。

每组都要从中按原顺序选出若干根木桩，使高度构成不下降序列。

要求输出：

最长不下降子序列长度；
达到这个长度的方案数。

思路

最直接的教学版做法是枚举所有子序列：

cpp

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53// brute.cpp：枚举所有子序列，统计最长不下降子序列长度和方案数，作为教学版和对拍基准程序。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int T;
int n;
int a[MAXN];
int best_len;
long long ways;

void dfs(int pos, int last_value, int cur_len) {
    if (pos > n) {
        if (cur_len > best_len) {
            best_len = cur_len;
            ways = 1;
        }
        else if (cur_len == best_len) {
            ways++;
        }
        return;
    }

    // 不选当前位置
    dfs(pos + 1, last_value, cur_len);

    // 选当前位置，必须保持不下降
    if (a[pos] >= last_value) {
        dfs(pos + 1, a[pos], cur_len + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }

        best_len = 0;
        ways = 0;
        dfs(1, -1000000000, 0);

        cout << best_len << ' ' << ways << '\n';
    }

    return 0;
}

但真正提交时，用 $O(n^2)$ 的 DP 更合适。

设：

dp[i]：以 i 结尾的最长不下降子序列长度
cnt[i]：达到 dp[i] 的方案数

初始化：

dp[i] = 1
cnt[i] = 1

DP 公式

把序列记为 $a_1,a_2,\ldots,a_n$ 。设 $dp_i$ 表示以第 $i$ 个木桩结尾的最长不下降子序列长度， $cnt_i$ 表示达到这个长度的方案数，则：

dp_i=1,\quad cnt_i=1

当 $j<i$ 且 $a_j\leqslant a_i$ 时，可以尝试从 $j$ 接到 $i$ ：

\begin{cases} dp_i=dp_j+1,\ cnt_i=cnt_j, & dp_j+1>dp_i,\\ cnt_i=cnt_i+cnt_j, & dp_j+1=dp_i. \end{cases}

最后令 $L=\max_i dp_i$ ，答案为：

\sum_{i:dp_i=L} cnt_i

然后枚举 j < i：

如果 a[j] <= a[i]，就可以从 j 转移到 i。

若 dp[j] + 1 > dp[i]，说明找到更优解，直接覆盖长度和方案数；
若 dp[j] + 1 == dp[i]，说明又找到一种同样优的接法，把方案数累加。

最后先求出全局最长长度，再把所有达到这个长度的结尾方案数加起来。

公式解释：dp_i 只关心最后选中的木桩是 i，因为前面的合法序列只需要满足高度不超过 a_i。当从 j 接到 i 得到更长长度时，旧方案全部失效，所以方案数改成 cnt_j；如果长度相同，就说明多了一批同样最优的结尾方案，要把方案数累加。

代码

cpp

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int T;
int n;
int a[MAXN];
int dp[MAXN];        // dp[i]：以 i 结尾的最长不下降子序列长度
long long cnt[MAXN]; // cnt[i]：达到 dp[i] 的方案数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            dp[i] = 1;
            cnt[i] = 1;
        }

        int best_len = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (a[j] <= a[i]) {
                    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];
                    }
                }
            }
            best_len = max(best_len, dp[i]);
        }

        long long ways = 0;
        for (int i = 1; i <= n; i++) {
            if (dp[i] == best_len) {
                ways += cnt[i];
            }
        }

        cout << best_len << ' ' << ways << '\n';
    }

    return 0;
}

复杂度

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

总结

这题是经典的最长不下降子序列 DP 扩展：

在维护长度的同时，再维护“达到这个最优长度的方案数”即可。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析