• 周三. 6月 29th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

信息学奥赛一本通【例9.3】求最长不下降序列 题解 动态规划

admin

11月 28, 2021

题目链接:http://ybt.ssoier.cn:8088/problem_show.php?pid=1259

题目大意:求一个序列的最长不下降子序列的长度,并输出任意一个最长不下降子序列。

解题思路:

定义状态 (f_i) 表示以 (a_i) 结尾的最长不下降子序列的长度。

(f_i = 1 + minlimits_{j = 1 o i-1(a_j le a_i)} f_j)

(f_i) 应该等于 (1)(i-1) 范围内的满足 (a_j le a_i)(f_j + 1) 的最大值。

这样就能够求出所有的 (f_i),则所有 (f_i) 的最大值就是最长不下降子序列的长度。

但是求出了长度之后还要输出任意一个满足条件的最长上升子序列。

这种情况下从前往后找是不对的,但是可以从后往前找,即再额外开一个状态 (p_i)(p_i) 表示以 (a_i) 结尾的最长不下降子序列中,(a_i) 的前一个数的下标。然后可以 递归地倒序输出这些数,具体见 output() 函数,output(x)会先去递归地 output (p_x)(即 (x) 的前一个位置),然后输出 (a_x)。(请认真理解 output 函数的递归解法)

然后这道题就解决了。

注意下面程序中的全局变量 (x) 表示的是满足 (f_x ge f_i(1 le i le n))(f_x) 是最大的那个),因为我要从 (x) 下标开始(调用 output 函数)递归往前(递归是往前的,但是输出是从前往后输出的,请注意递归函数的写法)。

示例程序:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 202;
int n, a[maxn], f[maxn], p[maxn], x;
void output(int x)
{
    if (p[x]) output(p[x]);
    printf("%d ", a[x]);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%d", a+i);
    for (int i = 1; i <= n; i ++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++)
        {
            if (a[j] <= a[i] && f[j]+1 > f[i])
            {
                f[i] = f[j] + 1;
                p[i] = j;
            }
        }
        if (f[i] > f[x]) x = i;
    }
    printf("max=%d
", f[x]);
    output(x);
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。