WillHou's Blog
0%

【专题】最长不下降子序列

发表于 分类于 Valine：
巨详细的最长不下降子序列解析

题目描述就不写了，这题实在太经典了。

下面重点分析算法：

大家都知道，这题是一道动态规划的入门题。众所周知，动态规划的题都可以通过搜索来骗分获得一定的分数。所以，对于这道题，我们仍然可以先用\(dfs\)写出来。代码较为暴力好懂，就不做解释。这个代码可以获得40-60分(视不同的OJ而定)

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
#include <iostream>
#include <cstring>
const int N = 109;
int n = 1, mx = -1, a[N], ans[N], anss[N];
void dfs(int x, int cnt)
{
    if (x > n)
        return ;
    if (cnt > mx)
    {
        mx = cnt;
        memcpy(anss, ans, N);
        // printf("mx=%d\n", mx);
        // for (int i = 1; i <= mx; i++)
        //     printf("%d ", ans[i]);
        // puts("");
        // puts("----------");
        // 这个注释可供大家看看这个程序的处理过程，以便小白更好的理解这段代码
    }
    for (int i = x; i <= n; i++)
        if (a[i] > ans[cnt])
        {
            ans[++cnt] = a[i];
            dfs(i+1, cnt);
            ans[cnt--] = 0;
        }
}
int main()
{
    while (~scanf("%d", a + n)) n++; n--;
    dfs(1, 0);
    printf("%d\n", mx);
    for (int i = 1; i <= mx; i++)
        printf("%d ", anss[i]);
    return 0;
}

测试样例：

测试样例

第一步. 确定状态

通常处理数列的题目, 我们都有现成的状态划分, 即从第一个数开始, 到第\(n\)个数结束. \[ f[i]代表前i个数中的最长不下降子序列的长度 \] 这时候有个问题: 第\(i\)个数我到底是取它还是舍它? 如果不包含\(i\), 那就没法写出状态转移方程.

不妨改成: \[ f[i]为前i个数的最长不下降序列的长度, 必须以第i个数结尾 \] 第二步. 状态转移方程

为了方便描述, 我们将输入定为为\(a\)数组, 储存动态规划结果数组定义为\(f\)数组

根据状态, 我们推导出状态转移方程: \(f[i]=max(f[j])+1\), 其中\(a[j]<a[i]且j<i\). 原因可以通过图示来说明.

易得\(f[1]=1\), 因为它独立成为一个最长不下降子序列

因为\(7<13\), 所以不存在\(a[j]<a[i]且j<i\).

此时, 存在\(7<9\), 所以\(mx=f[2]=1\). \(f[3]=mx+1=2\).

此时, 存在\(7<16,9<16\), 所以\(mx=max(f[2],f[3])=f[3]=2\). \(f[4]=mx+1=3\)

以此类推... 直至算到\(f[14]\), 结束循环. 此时, max{f[i]}即为答案.

因此, 有以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
const int N = 109;
int n = 1, ans, a[N], f[N];
int main()
{
    while (~scanf("%d", a + n)) n++; n--;
    for (int i = 1; i <= n; i++)
    {
        int mx = 0;
        for (int j = 1; j < i; j++)
            if (a[j]<a[i] and mx<f[j])
                mx = f[j];
        f[i] = mx + 1;
        if (f[i] > ans)
            ans = f[i];
    }
    printf("%d\n", ans);
    return 0;
}

部分OJ还要求输出最长不下降序列. 这似乎很难写, 实际上我们只需要加一个数组和一个变量就可以搞定.

为了方便描述, 我们将元素\(i\)的前驱定为\(pre[i]\).

找出所有满足\(a[j]<a[i]且j<i\)的\(j\). 求出max{a[j]}的下标\(id\), 那么记录\(pre[i]=id\). 可以通过图示来帮助更好的理解.

\(pre[1]\)没有前驱, 故\(pre[1]=0\).

\(7\)之前没有比它大的, 所以\(pre[2]=0\).

\(9\)之前有\(7<9\), 所以\(pre[3]=max\{a[j]\}的下标=a[2]的下标=2\).

\(16\)之前有\(7<16,9<16\), 所以\(pre[4]=max\{a[j]\}的下标=a[3]的下标=3\).

以此类推... 直至\(pre[14]\), 然后递归\(print(pre[max\{f[i]的下标\}])\), 直至\(x=0\)结束输出.

因此, 有如下代码: (代码中的\(sid\)即上文分析中的\(id\))

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
#include <iostream>
const int N = 109;
int n = 1, ans, sid, a[N], f[N], pre[N];
void print(int x)
{
    if (x == 0)
        return ;
    print(pre[x]);
    printf("%d ", a[x]);
}
int main()
{
    while (~scanf("%d", a + n)) n++; n--;
    for (int i = 1; i <= n; i++)
    {
        int mx = 0, id = 0;
        for (int j = 1; j < i; j++)
            if (a[j]<a[i] and mx<f[j])
                mx = f[j], id = j;
        f[i] = mx + 1, pre[i] = id;
        if (f[i] > ans)
        {
            ans = f[i];
            sid = i;
        }
    }
    printf("%d\n", ans);
    print(sid);
    return 0;
}