问题：

最长K序列递增子序列

贡念

2023-03-14

我在阅读了允许K个异常的最长递增子序列后创建了这个线程。我意识到提问的人并没有真正理解这个问题，因为他指的是一个链接，该链接解决了“允许一次更改的最长递增子数组”问题。所以他得到的答案实际上与李的问题无关。

假设给定一个长度为N的数组A。查找允许K个异常的最长递增子序列。

示例：N=9，K=1

A=[3,9,4,5,8,6,1,3,7]

答案：7

说明：

最长递增子序列为：3,4,5,8（或6），1（异常），3,7-

A=[5,6,4,7,3,9,2,5,1,8,7]

答案：8

如果K=1，则只允许一个异常。如果使用了用于计算O（NlogN）中最长递增子序列的已知算法（单击此处查看该算法），那么我们可以计算阵列A每个元素从[0]到[N-1]的LIS。我们将结果保存在大小为N的新阵列L中。查看示例N.1，L阵列将为：L=[1,2,2,3,4,4,4,4,5]。

使用反向逻辑，我们计算数组R，其中每个元素包含从N-1到0的当前最长递减序列。

LIS只有一个例外，即sol=max（sol，L[i]R[i 1]），其中sol初始化为sol=L[N-1]。因此，我们从0开始计算LIS，直到索引i（异常），然后停止并启动一个新的LIS，直到N-1。

A=[3,9,4,5,8,6,1,3,7]

L=[1,2,2,3,4,4,4,4,5]

R=[5,4,4,3,3,3,3,2,1]

Sol = 7

init: sol = L[N]= 5

i=0 : sol = max(sol,1+4) = 5 
i=1 : sol = max(sol,2+4) = 6
i=2 : sol = max(sol,2+3) = 6
i=3 : sol = max(sol,3+3) = 6
i=4 : sol = max(sol,4+3) = 7
i=4 : sol = max(sol,4+3) = 7
i=4 : sol = max(sol,4+2) = 7
i=5 : sol = max(sol,4+1) = 7

复杂度：O（NlogN NlogN N）=O（NlogN）

因为数组R、L需要NlogN时间来计算，我们还需要Θ（N）才能找到sol。

k=1问题代码

#include <stdio.h>
#include <vector>

std::vector<int> ends;

int index_search(int value, int asc) {
    int l = -1;
    int r = ends.size() - 1;
    while (r - l > 1) { 
        int m = (r + l) / 2; 
        if (asc && ends[m] >= value) 
            r = m; 
        else if (asc && ends[m] < value)
            l = m;
        else if (!asc && ends[m] <= value)
            r = m;
        else
            l = m;
    } 
    return r;
}

int main(void) {
    int n, *S, *A, *B, i, length, idx, max;

    scanf("%d",&n);
    S = new int[n];
    L = new int[n];
    R = new int[n];
    for (i=0; i<n; i++) {
        scanf("%d",&S[i]);
    }

    ends.push_back(S[0]);
    length = 1;
    L[0] = length;
    for (i=1; i<n; i++) {
        if (S[i] < ends[0]) {
            ends[0] = S[i];
        }
        else if (S[i] > ends[length-1]) {
            length++;
            ends.push_back(S[i]);
        }
        else {
            idx = index_search(S[i],1);
            ends[idx] = S[i];
        }
        L[i] = length;
    }

    ends.clear();
    ends.push_back(S[n-1]);
    length = 1;
    R[n-1] = length;
    for (i=n-2; i>=0; i--) {
        if (S[i] > ends[0]) {
            ends[0] = S[i];
        }
        else if (S[i] < ends[length-1]) {
            length++;
            ends.push_back(S[i]);
        }
        else {
            idx = index_search(S[i],0);
            ends[idx] = S[i];
        }
        R[i] = length;
    }

    max = A[n-1];
    for (i=0; i<n-1; i++) {
        max = std::max(max,(L[i]+R[i+1]));
    }

    printf("%d\n",max);
    return 0;
}

我提供了一个K=1的算法。我不知道如何更改上述算法以适用于K异常。如果有人能帮助我，我会很高兴。

赵君植

2023-03-14

这个答案是从我在计算机科学堆栈交换中对类似问题的回答修改而来的。

最多有k个异常的LIS问题允许使用拉格朗日松弛的O（n log²n）算法。当k大于log n时，这在O（nk log n）DP上渐近改进，我们也将简要解释。

设DP[a][b]表示最长递增子序列的长度，最多有b个例外（前一个整数大于下一个整数的位置）终止于元素 ~~b ~~a。该DP不涉及算法，但定义它使证明算法更容易。~~~~

为了方便起见，我们假设所有html" target="_blank">元素都是不同的，并且数组中的最后一个元素是其最大值。请注意，这并没有限制我们，因为我们可以将m/2n添加到每个数字的第m个外观，并将无穷大附加到数组中，然后从答案中减去一。设V为1的置换

~~为了解决O（nk log n）中的问题，我们保持不变，即已为b计算DP[a][b]~~

~~我们有DP[i][j]=1 max（DP[i'][j]，DP[x][j-1]），其中我们经过i'，x~~

~~这是该算法的C实现。请注意，此实现并不假设数组的最后一个元素是其最大值，或者数组不包含重复项。~~

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

// Fenwick tree for prefix maximum queries
class Fenwick {
    private:
        vector<int> val;
    public:
        Fenwick(int n) : val(n+1, 0) {}

        // Sets value at position i to maximum of its current value and 
        void inc(int i, int v) {
            for (++i; i < val.size(); i += i & -i) val[i] = max(val[i], v);
        }

        // Calculates prefix maximum up to index i
        int get(int i) {
            int res = 0;
            for (++i; i > 0; i -= i & -i) res = max(res, val[i]);
            return res;
        }
};

// Binary searches index of v from sorted vector
int bins(const vector<int>& vec, int v) {
    int low = 0;
    int high = (int)vec.size() - 1;
    while(low != high) {
        int mid = (low + high) / 2;
        if (vec[mid] < v) low = mid + 1;
        else high = mid;
    }
    return low;
}

// Compresses the range of values to [0, m), and returns m
int compress(vector<int>& vec) {
    vector<int> ord = vec;
    sort(ord.begin(), ord.end());
    ord.erase(unique(ord.begin(), ord.end()), ord.end());
    for (int& v : vec) v = bins(ord, v);
    return ord.size();
}

// Returns length of longest strictly increasing subsequence with at most k exceptions
int lisExc(int k, vector<int> vec) {
    int n = vec.size();
    int m = compress(vec);
    vector<int> dp(n, 0);
    for (int j = 0;; ++j) {
        Fenwick fenw(m+1); // longest subsequence with at most j exceptions ending at this value
        int max_exc = 0; // longest subsequence with at most j-1 exceptions ending before this
        for (int i = 0; i < n; ++i) {
            int off = 1 + max(max_exc, fenw.get(vec[i]));
            max_exc = max(max_exc, dp[i]);

            dp[i] = off;
            fenw.inc(vec[i]+1, off);
        }
        if (j == k) return fenw.get(m);
    }
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> vec(n);
    for (int i = 0; i < n; ++i) cin >> vec[i];

    int res = lisExc(k, vec);
    cout << res << '\n';
}

~~现在我们将返回O（n log²n）算法。选择某个整数0~~

~~注意，MINB[a][r]~~

~~为此，我们需要一个存储元组P[i]=（v_i，low_i，high_i）的段树，并支持以下操作：~~

~~设置元组P[i]的值~~

~~这很容易实现，每个操作的复杂度为O（log n），假设对段树有一定的熟悉。有关详细信息，请参阅下面的算法实现。~~

现在我们将展示如何在O（n log n）中计算DP’，MINB和MAXB。修复r。构建最初包含n 1个空值的段树（-INF，INF，-INF）。对于小于当前位置i的j，我们保持P[V[j]=（DP’[j]，MINB[j]，MAXB[j]）。如果r

从1到n循环i。有两种类型的子序列以i结尾：前一个元素大于V[i]的子序列和小于V[i]的子序列。为了解释第二种，查询[0， V[i]]范围内的段树。假设结果是（v_1，low_1，high_1）。设置off1=（v_11，low_1，high_1）。对于第一种，查询[V[i]， n]范围内的段树。假设结果是（v_2，low_2，high_2）。设置2=（v_21-r，low_21，high_21），其中我们因创建异常而受到r的惩罚。

~~然后我们将off1和off2合并为off。如果关闭1。v~~

~~由于我们在每个i处进行两个段树查询，因此总共需要O（n log n）个时间。通过归纳很容易证明我们计算了正确的值DP’，MINB和MAXB。~~

~~所以简而言之，算法是：~~

~~预处理，修改值，使其形成排列，最后一个值是最大值。~~

~~二进制搜索正确的r，初始界限为0~~

~~使用空值初始化段树，设置DP“[0]、MINB[0]和MAXB[0]。~~

~~在步骤i，从i=1到n的循环~~

~~查询段树的范围[0，V[i]]和[V[i]，n]，~~

基于这些查询计算DP’[i]、MINB[i]和MAXB[i]，以及

将段树中位置V[i]处的值设置为元组（DP’[i]、MINB[i]、MAXB[i]）

~~如果MINB[n][r]~~

~~否则，如果MAXB[n][r]~~

~~这是该算法的C实现。它还找到了最优子序列。~~

  
   
        #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    using ll = long long;
    const int INF = 2 * (int)1e9;

    pair<ll, pair<int, int>> combine(pair<ll, pair<int, int>> le, pair<ll, pair<int, int>> ri) {
        if (le.first < ri.first) swap(le, ri);
        if (ri.first == le.first) {
            le.second.first = min(le.second.first, ri.second.first);
            le.second.second = max(le.second.second, ri.second.second);
        }
        return le;
    }

    // Specialised range maximum segment tree
    class SegTree {
        private:
            vector<pair<ll, pair<int, int>>> seg;
            int h = 1;

            pair<ll, pair<int, int>> recGet(int a, int b, int i, int le, int ri) const {
                if (ri <= a || b <= le) return {-INF, {INF, -INF}};
                else if (a <= le && ri <= b) return seg[i];
                else return combine(recGet(a, b, 2*i, le, (le+ri)/2), recGet(a, b, 2*i+1, (le+ri)/2, ri));
            }
        public:
            SegTree(int n) {
                while(h < n) h *= 2;
                seg.resize(2*h, {-INF, {INF, -INF}});
            }
            void set(int i, pair<ll, pair<int, int>> off) {
                seg[i+h] = combine(seg[i+h], off);
                for (i += h; i > 1; i /= 2) seg[i/2] = combine(seg[i], seg[i^1]);
            }
            pair<ll, pair<int, int>> get(int a, int b) const {
                return recGet(a, b+1, 1, 0, h);
            }
    };

    // Binary searches index of v from sorted vector
    int bins(const vector<int>& vec, int v) {
        int low = 0;
        int high = (int)vec.size() - 1;
        while(low != high) {
            int mid = (low + high) / 2;
            if (vec[mid] < v) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    // Finds longest strictly increasing subsequence with at most k exceptions in O(n log^2 n)
    vector<int> lisExc(int k, vector<int> vec) {
        // Compress values
        vector<int> ord = vec;
        sort(ord.begin(), ord.end());
        ord.erase(unique(ord.begin(), ord.end()), ord.end());
        for (auto& v : vec) v = bins(ord, v) + 1;

        // Binary search lambda
        int n = vec.size();
        int m = ord.size() + 1;
        int lambda_0 = 0;
        int lambda_1 = n;
        while(true) {
            int lambda = (lambda_0 + lambda_1) / 2;
            SegTree seg(m);
            if (lambda > 0) seg.set(0, {0, {0, 0}});
            else seg.set(0, {0, {0, INF}});

            // Calculate DP
            vector<pair<ll, pair<int, int>>> dp(n);
            for (int i = 0; i < n; ++i) {
                auto off0 = seg.get(0, vec[i]-1); // previous < this
                off0.first += 1;

                auto off1 = seg.get(vec[i], m-1); // previous >= this
                off1.first += 1 - lambda;
                off1.second.first += 1;
                off1.second.second += 1;

                dp[i] = combine(off0, off1);
                seg.set(vec[i], dp[i]);
            }

            // Is min_b <= k <= max_b?
            auto off = seg.get(0, m-1);
            if (off.second.second < k) {
                lambda_1 = lambda - 1;
            } else if (off.second.first > k) {
                lambda_0 = lambda + 1;
            } else {
                // Construct solution
                ll r = off.first + 1;
                int v = m;
                int b = k;
                vector<int> res;
                for (int i = n-1; i >= 0; --i) {
                    if (vec[i] < v) {
                        if (r == dp[i].first + 1 && dp[i].second.first <= b && b <= dp[i].second.second) {
                            res.push_back(i);
                            r -= 1;
                            v = vec[i];
                        }
                    } else {
                        if (r == dp[i].first + 1 - lambda && dp[i].second.first <= b-1 && b-1 <= dp[i].second.second) {
                            res.push_back(i);
                            r -= 1 - lambda;
                            v = vec[i];
                            --b;
                        }
                    }
                }
                reverse(res.begin(), res.end());
                return res;
            }
        }
    }

    int main() {
        int n, k;
        cin >> n >> k;

        vector<int> vec(n);
        for (int i = 0; i < n; ++i) cin >> vec[i];

        vector<int> ans = lisExc(k, vec);
        for (auto i : ans) cout << i+1 << ' ';
        cout << '\n';
    }

~~我们现在将证明这两种说法。我们希望证明这一点~~

~~DP’[a][r]=DP[a][b]-rb当且仅当MINB[a][r]~~

~~对于所有a，k，存在一个整数r，0~~

~~这两个都是从问题的凹性出发的。Con洞意味着DP[a][k 2]-DP[a][k 1]~~

~~固定a和r。设置f（b）=DP[a][b]-rb，d（b）=f（b 1）-f（b）。我们有d（k 1）~~

~~为了证明第二个，设置r=DP[a][k 1]-DP[a][k]并像以前一样定义f， d。那么d（k）=0，因此d（i）~~

~~证明凹度更加困难。有关证明，请参阅我在cs上的回答。stackexchange。~~

最长K序列递增子序列

共有1个答案

相关问答

相关文章

相关阅读

相关工具

相关文档