【专题】最长不下降序列(LIS)

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

下面重点分析算法：

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

#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]}即为答案.

因此, 有以下代码:

#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, id = 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$)

#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;
}

#创作不易, 赏个赞呗#