NOIP 2010 普及组 最后一题 - 伪最长不降子序列

题目描述

给定一个长度为 n 的数组 a1, a2, ..., an，以及一个整数 m。定义数组的“伪最长不降子序列”长度为它的最长不降子序列的长度加上 m，即：如果这个数组的最长不降子序列长度为 k，则它的伪最长不降子序列长度为 k+m。

现在，你可以任意改变数组中的元素，使得它的“伪最长不降子序列”长度最小。请问最小的“伪最长不降子序列”长度是多少？

输入格式

第一行包含两个整数 n，m。

第二行包含 n 个整数 a1, a2, ..., an。

输出格式

输出一个整数，表示最小的“伪最长不降子序列”长度。

数据范围

1≤n≤1000, 1≤m≤1000, 1≤ai≤1000

样例

输入样例： 4 1 2 1 3 2

输出样例： 3

算法

(二分+贪心) O(nlog²n)

首先，我们考虑最长不降子序列的求解方法，即用二分查找的方式来求解，时间复杂度为 O(nlogn)。

接着，我们考虑如何修改数组中的元素来使得其“伪最长不降子序列”长度最小。假设我们现在已经确定了前 k-1 个数字，且已经求出了这个前缀的最长不降子序列长度 len_{k-1}，现在我们需要在 a_k 之前插入一个数字，使得插入后的这个前缀的最长不降子序列长度为 len_k，且 len_k-len_{k-1}=1。这样插入一个数字后，m 也会多加 1，因此，我们只需要保证所有的插入操作所增加的长度之和不超过 m 即可。

根据贪心的思想，我们优先选择那些可以使得前缀当前最长不降子序列尽可能的短的数字进行插入。也就是说，对于一个数字 a_k，我们希望在其之前插入一个数字 a_{p_k}，使得这个前缀的最长不降子序列长度尽可能的短，即 len_{p_k}+1=len_k 且在满足这个条件的前提下，p_k 越小越好。

现在的问题是，对于一个数字 a_k，如何快速找到这个数字的合适插入位置。

我们考虑维护一个长度为 i 的不降子序列的最小末尾数字 tail_i。对于一个数字 a_k，我们可以通过二分查找的方式，找到一个最小的位置 p，使得 tail_p 大于等于 a_k，然后将 a_k 插入到 p 的位置上。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1005;

int n, m, a[MAXN], tail[MAXN], len;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    tail[1] = a[1];
    len = 1;
    for (int i = 2; i <= n; ++i) {
        if (a[i] >= tail[len]) {
            tail[++len] = a[i];
        } else {
            int p = lower_bound(tail + 1, tail + len + 1, a[i]) - tail;
            tail[p] = a[i];
        }
    }
    cout << len + m << endl;
    return 0;
}