51Nod 1218. 最长递增子序列 V2(思路题)

日付: 10月 25, 2018

[最长递增子序列 V2问题 - 51Nod](https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1218)
## Problem
一个数组，找出一定与可能出现在最长递增子序列中的数。

## Solution
一个数如果在最长递增子序列中出现，它的位置是一定的(否则可以构造出更长的序列)，如果一个数在最长递增子序列中出现的位置有其他数和它相同，这个数就是可能出现，否则就是必定出现。

按正序求最长递增，逆序求最长递减，记录每个数出现的位置。用一个数组维护各位置出现的次数，对于出现在最长递增子序列中的数，其位置次数加1。最后再遍历一般所有数，检查是否出现在最长递增子序列中，并检查其位置的次数是否为1。

```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main() {
    int n;
    scanf("%d", &n);
    vector<int> A(n + 1), L(n + 1), R(n + 1);
    for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
    vector<int> Tmp(n + 1, INT_MAX);
    int len = 1;
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(Tmp.begin(), Tmp.end(), A[i]) - Tmp.begin();
        L[i] = p + 1;
        len = max(len, L[i]);
        Tmp[p] = A[i];
    }
    fill(Tmp.begin(), Tmp.end(), INT_MAX);
    for (int i = n; i >= 1; i--) {
        int p = lower_bound(Tmp.begin(), Tmp.end(), -A[i]) - Tmp.begin();
        R[i] = p + 1;
        Tmp[p] = -A[i];
    }
    vector<int> Cnt(n + 1);
    for (int i = 1; i <= n; i++) if (L[i] + R[i] == len + 1) Cnt[L[i]]++;
    vector<int> T1, T2;
    for (int i = 1; i <= n; i++) {
        if (L[i] + R[i] != len + 1) continue;
        if (Cnt[L[i]] == 1) T2.push_back(i);
        else T1.push_back(i);
    }
    printf("A:");
    for (size_t i = 0; i < T1.size(); i++) printf("%d%c", T1[i], " \n"[i + 1 == T1.size()]);
    printf("B:");
    for (size_t i = 0; i < T2.size(); i++) printf("%d%c", T2[i], " \n"[i + 1 == T2.size()]);
    return 0;
}
```
</details>

KONGROOの基地

このブログを検索

51Nod 1218. 最长递增子序列 V2(思路题)

コメント

コメントを投稿