很有（\(bu\)）质（\(hui\)）量（\(xie\)）的一个题目。
第一问：求最少改变几个数能把一个随机序列变成单调上升序列。
\(Solution:\)似乎是一个结论？如果两个数\(A_i\)和\(A_j\)可以保留（\(i > j, A_i > A_j\)），即中间其他数都可以通过修改成为\([A_i, A_j]\)区间内的一个数，那么一定有\(i - j <= A_i - A_j\)，即\(A_i - i >= A_j - j\)。这个东西我们可以设为数列\(B\)，求一个最长不下降子序列就可以了。
（其实我中间智障了写成了最长上升子序列居然还有\(90ptshhhhh\)）
第二问：结论看这里。有了第一问的铺垫其实并不难想，但是问题在于可以有很多种最长不下降子序列，该怎么办？
我们考虑对答案\(DP\)，设\(f_x\)为前\(x\)个数有序化的最小代价（其中\(x\)一定是一个子序列内的点），然后来一发轻松愉快的\(DP\)。由于数据完全随机，所以可以剪枝过去。（虽然就是不随机恐怕也很难卡满就是了\(QwQ\)）
#include <bits/stdc++.h>
using namespace std;#define int long long
const int N = 35000 + 5;
const int INF = 0x3f3f3f3f;int n, A[N], B[N], Longest[N];vector <int> q, G[N];
vector <int> :: iterator it;int solve1 () {for (int i = 1; i <= n + 1; ++i) {if (q.empty () || B[i] >= q[q.size () - 1]) {q.push_back (B[i]); Longest[i] = q.size ();} else {it = upper_bound (q.begin (), q.end (), B[i]);*it = B[i]; Longest[i] = it - q.begin () + 1;}G[Longest[i]].push_back (i); }// Longest[i] : 以 i 结尾的最长不下降子序列return q.size () - 1; // 可以保留的数的个数
} int dp[N], hl[N], hr[N]; // hl[i] -> 从 l 到 i 都选择变成左端点值的代价, hr 同理 int solve2 () {memset (dp, 0x3f, sizeof (dp));dp[0] = 0; G[0].push_back (0);for (int v = 1; v <= n + 1; ++v) {for (int i = 0; i < G[Longest[v] - 1].size (); ++i) {int u = G[Longest[v] - 1][i];
// cout << "u = " << u << " v = " << v << endl;if (v < u || B[v] < B[u]) continue;hl[u] = hr[v] = 0;for (int k = u + 1; k < v; ++k) {hl[k] = hl[k - 1] + abs (B[k] - B[u]);}for (int k = v - 1; k > u; --k) {hr[k] = hr[k + 1] + abs (B[k] - B[v]);}for (int k = u; k < v; ++k) {dp[v] = min (dp[v], dp[u] + hl[k] + hr[k + 1]);}}}return dp[n + 1];
}signed main () {
// freopen ("data.in", "r", stdin);
// freopen ("data.out", "w", stdout);cin >> n;B[0] = -INF, B[n + 1] = INF;for (int i = 1; i <= n; ++i) {cin >> A[i]; B[i] = A[i] - i;}cout << n - solve1 () << endl; // 对数列 B 做最长不下降子序列 cout << solve2 () << endl; // ans
}
