关于最长上升子序列——可能出现的元素与必定出现的元素

题目描述

给定一个长度为$n$的序列$a_1,a_2,\cdots ,a_n$请求出它的最长上升子序列的长度，以及有多少个位置上的元素可能出现在最长上升子序列中，多少个位置上的元素一定出现在最长上升子序列中？
例如，给定序列 $3,1,2,5,4$ 中:$1,2,5$与$1,2,4$均为满足条件的最长上升子序列，该序列的最长上升子序列的长度为$3$。元素$1,2,4,5$均有可能出现在最长上升子序列中，故有$4$个位置上的元素可能出现在最长上升子序列中，而元素$1,2$必然出现在最长上升子序列中，故有$2$个位置上的元素一定出现在最长上升子序列中。

输入格式

输入共两行：输入第一行，一个整数$n$，表示给定序列元素个数输入第二行，$n$个正整数，分别表示$a_1,a_2,\cdots ,a_n$​。

输出格式

输出共一行：第一行：输出三个数字，分别表示最长上升子序列长度，可能出现在最长上升子序列中的元素位置个数，及必然出现在最长上升子序列中元素位置个数，用空格隔开。

输入样例

5
3 1 2 5 4

输出样例

3 6 2

数据范围

对于 $20\%$的数据，$1\le n\le 10$
对于 $70\%$的数据，$1\le n\le 10^4$
对于 $100\%$的数据，$1\le n\le 10^5,1\le a_i\le 10^9$

题目解答

这是一道可以用网络流做的题目，但作为一个蒟蒻的我，肯定是写不出来的。所以这道题其实也是可以用动态规划来解决的。求最长上升子序列长度是相对简单的，所以我们先分析一下第二个问题：

• 如果一个数会出现在某一个LIS中，那么它就是可能出现的
• 设$d{p}_i$为以$a_i$结尾的LIS的长度，$dp{2}_i$为以$a_i$开头的LIS的长度
• 若$a$序列的LIS长度记为$len$，那么如果$d{p}_i+dp{2}_i$等于$len+1$，那么$a_i$就是可能存在于某个LIS中的一个元素
• $dp$数组可以直接二分$O(n\log n)$求，而$dp2$数组则可以逆序求一遍LDS

当我们分析完第二个问题时，一些聪明的小盆友们肯定已经想出第三个问题的方法了：

• 对于一个一定存在于LIS的元素$a_i$，只有它能将左边$d{p}_i$个元素和右边$dp{2}_i$个元素进行衔接
• 如果有一个$d{p}_j$与$d{p}_i$相等，那么$dp{2}_j$就一定与$dp{2}_i$相等，它们必定不属于同一个LIS
• 所以，它的$d{p}_i$或$dp{2}_i$一定是唯一且不重复的，可以用一个$cnt$数组进行标记

AC代码

#include <bits/stdc++.h>
using namespace std;
int n, len, len2, ans, ans2, a[100005], rec[100005], dp[100005], dp2[100005];
unordered_map<int, int> cnt;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    memset(rec, 0, sizeof rec);
    for (int i = 1; i <= n; i++) // 正序求一遍LIS，求dp数组
    {
        int idx = lower_bound(rec + 1, rec + len + 1, a[i]) - rec;
        rec[idx] = a[i], dp[i] = idx, len = max(len, idx);
    }
    memset(rec, 0, sizeof rec);
    for (int i = n; i >= 1; i--) // 逆序求一遍LDS，求dp2数组
    {
        int idx = lower_bound(rec + 1, rec + len2 + 1, a[i], greater<int>()) - rec;
        rec[idx] = a[i], dp2[i] = idx, len2 = max(len2, idx);
    }
    for (int i = 1; i <= n; i++)
        if (dp[i] + dp2[i] == len + 1) // 若dp[i]+dp2[i] == len + 1，则为可能出现的
            ans++, cnt[dp[i]]++; // 用cnt数组记录dp[i]
    for (int i = 1; i <= n; i++)
        if (dp[i] + dp2[i] == len + 1 && cnt[dp[i]] == 1) // 若dp[i]仅出现一次，则为一定出现的
            ans2++;
    printf("%d %d %d", len, ans, ans2);
    return 0;
}

本期博客就到这里，若注解有误，还请各位大佬多多指教！