此答案从my answer修改为Computer Science Stackexchange上的类似问题。
最多有k个例外的LIS问题允许使用拉格朗日松弛法进行O（nlog²n）算法。当k大于log n时，这在O（nk log n）DP上渐近改善，我们还将对此进行简要说明。
让DP [a] [b]表示最长的递增子序列的长度，最多b个例外（前一个整数大于下一个整数的位置），其结尾是元素 b a。该DP不包含在算法中，但是对其进行定义使算法的证明更加容易。
为方便起见，我们将假定所有元素都是不同的，并且数组中的最后一个元素为其最大值。请注意，这并不限制我们，因为我们可以将m / 2n添加到每个数字的第m个出现，然后将无穷大附加到数组并从答案中减去1。令V为排列，其中1
要解决O（nk log n）中的问题，我们保持对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（nlog²n）算法。选择一些整数0
请注意，如果r = MINB [a] [r']和MAXB [a] [r]> = MAXB [a] [r']，因此我们假设在两个声明的结果中，我们可以尝试对r进行二进制搜索，尝试使用O（log n）值。因此，如果我们能够在O（n log n）的时间内计算DP'，MINB和MAXB，就可以实现复杂度O（nlog²n）。
为此，我们将需要一个存储元组P [i] =（v_i，low_i，high_i）并支持以下操作的分段树：
-
给定范围[a，b]，找到该范围内的最大值（最大v_i，a
-
设置元组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> 0，则将DP'[0] = 0，MINB [0] = 0并将MAXB [0]设置为0，否则将INF和P [0] =（DP'[0]，MINB [0]，MAXB [ 0]）。
将i从1循环到n。有两种以i结尾的子序列：上一个元素大于V [i]的子序列和小于V [i]的子序列。要说明第二种，请查询范围为[0，V [i]]的段树。令结果为（v_1，low_1，high_1）。设置为1 =（v_1 + 1，low_1，high_1）。对于第一种，查询范围为[V [i]，n]的段树。令结果为（v_2，low_2，high_2）。设置off2 =（v_2 + 1-r，low_2 + 1，high_2 + 1），在这里我们因创建异常而受到r的惩罚。
然后我们将off1和off2合并为off。如果off1.v> off2.v设置为off = off1，并且如果off2.v> off1.v设置为off = off2。否则，设置为off =（off1.v，min（off1.low，off2.low），max（off1.high，off2.high））。然后设置DP'[i] = off.v，MINB [i] = off.low，MAXB [i] = off.high和P [i] = off。
由于我们在每个i上进行两个分段树查询，因此总共花费O（n log n）时间。通过归纳很容易证明我们计算出正确的值DP'，MINB和MAXB。
简而言之，算法是：
-
预处理，修改值，使其形成排列，最后一个值是最大值。
-
二进制搜索正确的r，初始范围为0
-
使用空值初始化分段树，设置DP'[0]，MINB [0]和MAXB [0]。
-
从i = 1到n，在步骤i
- 查询段树的范围[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] k，则正确的r大于当前r。更新r的边界并返回到步骤1。
这是此算法的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,int>> le,pair<ll,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,int>>> seg;
int h = 1;
pair<ll,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,2*i+1,(le+ri)/2,ri));
}
public:
SegTree(int n) {
while(h < n) h *= 2;
seg.resize(2*h,{-INF,-INF}});
}
void set(int i,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,int>> get(int a,int b) const {
return recGet(a,b+1,1,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());
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}});
else seg.set(0,INF}});
// Calculate DP
vector<pair<ll,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
这两者都是从问题的凹入中得出的。凹度是指对于所有a，k，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） = f（i）。因此，d（x）
为证明第二个，设置r = DP [a] [k + 1]-DP [a] [k]并如前定义f，d。然后d（k）= 0，因此对于i = 0，对于i> k，d（i）
证明凹度更加困难。有关证明，请参见c.stackexchange上的my answer。
,
幼稚的动态程序可以考虑为第max_j[i][l]个输入元素存储最大索引i的概念表j ≤ i，这样长度l的递增子序列可以在A[j]和A[i]之间形成。我们有
max_j[i][l] = max(max_j[v][l-1])
for min(A[0..i-1]) ≤ v < A[i]
我们的函数/表f[i][k]可以表示为
f[i][k] = max(
// Skip this element
f[i - 1][k],// Contribute to a sequence
l + f[j - 1][k - 1]
)
forall 1 < l ≤ longest increasing
subsequence ending at A[i]
(ideally,although there are cheap heuristics)
where j = max_j[i][l]
我声称对l的遍历将是单峰的，这意味着我们可以对其进行二进制搜索。随着我们增加l，我们将j（区间的左索引）移到更左侧，并且由于f是单调的（总是在上一个值或更大的值之间进行选择），会到达起点，或者l的成本过高，因此必须设置较大的间隔，以使f超出最佳点。
,
您可以修改标准算法以获取O（k * n * logn），尽管我不确定，我认为二进制搜索仅对n执行一次，而不对k次执行。因为您不需要知道实际的序列就不需要跟踪列表，所以知道最后一个数字就足够了，这使它稍微容易一些。这是带有注释的代码（适用于您的示例，但我不确定边缘情况100％）：
private static int lis(int[] numbers,int k) {
if (numbers.length <= k + 1)
return numbers.length;
int[][] active = new int[k + 1][numbers.length + 1]; // exceptions,length,last number
int[] start = new int[k + 1]; // at which length the lists with x exceptions start
int[] end = new int[k + 1]; // at which length the lists with x exceptions end
// add first number
active[0][1] = numbers[0];
start[0] = 1;
end[0] = 1;
// go through the rest of the numbers using the standard algorithm
for (int i = 1; i < numbers.length; i++) {
for (int ex = k; ex >= 0; ex--) {
// can we just extend?
if (end[ex] > 0 && active[ex][end[ex]] < numbers[i]) {
active[ex][++end[ex]] = numbers[i];
// can we create a better list using the largest with one less exception?
} else if (ex > 0 && end[ex - 1] > 0 && active[ex - 1][end[ex - 1]] > numbers[i]) {
if (end[ex] == 0) { // no entries yet for this number of exceptions
end[ex] = end[ex - 1] + 1;
start[ex] = end[ex];
active[ex][end[ex]] = numbers[i];
} else if (active[ex][end[ex - 1] + 1] > numbers[i]) {
active[ex][end[ex - 1] + 1] = numbers[i];
}
// did we reach a new minimum?
} else if (ex == 0 && active[0][1] > numbers[i]) {
active[0][1] = numbers[i];
// update value using binary search like the standard algorithm
} else if (start[ex] > 0 && numbers[i] > active[ex][start[ex]]) {
int left = start[ex];
int right = end[ex];
while (left + 1 != right) {
int mid = left + right / 2;
if (active[ex][mid] < numbers[i]) {
left = mid;
} else {
right = mid;
}
}
if (active[ex][right] > numbers[i]) {
active[ex][right] = numbers[i];
}
}
}
}
return Arrays.stream(end).max().getAsInt();
}
本文链接：https://www.f2er.com/2864559.html
