• $O(n^2)$ 的最长不上升子序列问题
• 70 分，会超时

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	
	// 要尽可能的少改数  =>  尽可能多的保留数
	// a[i] <= a[j] + (i - j) * k    =>    a[i] - i * k <= a[j] - j * k
	
	// 计算出每个人的 a[i] - k * i
	for (int i = 0; i < n; i++) a[i] = a[i] - k * i;
	
	// dp[i] 表示 (a[i], .... a[n - 1]) 中 保留 a[i] 时, 最多能保留的个数
	vector<int> dp(n, 1);
	for (int i = n - 1; i >= 0; i--) {
		
		dp[i] = 1;
		for (int j = i + 1; j < n; j++) {
			// 如果 a[j] <= a[i], 那么 a[j] 就能接在 a[i] 后面
			if (a[j] <= a[i]) dp[i] = max(dp[i], dp[j] + 1);
		}
	}
	cout << n - *max_element(dp.begin(), dp.end()) << '\n';
	
	return 0;
}

• 用 sort()，unique()，erase()，lower_bound() 离散化一个数组

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n = 6;
	vector<int> a = {15, 14, 14, 16, 11, 11};
	
	// 把 a 数组复制一遍到 c 数组, 用于离散化
	vector<int> c = a;
	
	cout << "原数组:\n";
	for (int i = 0; i < (int) c.size(); i++) cout << c[i] << ' ';
	cout << "\n\n";
	
	// 将 c 从小到大排序, c = [11, 11, 14, 14, 15, 16]
	sort(c.begin(), c.end());
	
	cout << "排序后:\n";
	for (int i = 0; i < (int) c.size(); i++) cout << c[i] << ' ';
	cout << "\n\n";
	
	// unique() 用于将一个排好序的数组去重
	// 把可以删除的数放到后面, 并返回第一个可以删除的数的迭代器
	auto it = unique(c.begin(), c.end());
	
	cout << "unique() 后:\n";
	for (int i = 0; i < (int) c.size(); i++) cout << c[i] << ' ';
	cout << "\n\n";
	
	// 将 c 后面可以删除的数删除
	c.erase(it, c.end());
	
	cout << "删除重复的数后:\n";
	for (int i = 0; i < (int) c.size(); i++) cout << c[i] << ' ';
	cout << "\n\n";
	
	// 排序去重后, c 数组中数的个数
	int e = c.size();
	cout << "排序去重后数组的大小= " << e << "\n\n";
	
	for (int i = 0; i < (int) a.size(); i++) {
		// 把 a[i] 离散化到 [1, e]
		a[i] = lower_bound(c.begin(), c.end(), a[i]) - c.begin() + 1;
	}
	
	cout << "离散化后:\n";
	for (int i = 0; i < (int) a.size(); i++) cout << a[i] << ' ';
	cout << "\n\n";
	
	
	/*
	将 a 数组 离散化, 可以简写成下面的样子:
	vector<int> c = a;
	sort(c.begin(), c.end());
	c.erase(unique(c.begin(), c.end()), c.end());
	for (int i = 0; i < n; i++) {
		a[i] = lower_bound(c.begin(), c.end(), a[i]) - c.begin() + 1;
	}
	*/
	return 0;
}