#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 35e3 + 10;
 
int a[N], b[N];
int mn_end[N], len;   // [i]：长度为 i 的最长不降子序列（LIS）的最小结尾
int L[N];            // [i]：以 i 点为结尾 LIS 的长度 
vector<int> G[N];    // LIS 长度桶 
LL sumi[N], sumj[N];   // [k]：i 到 k 全部改成 b[i] / b[j] 的代价 
LL dp[N];             // [i]：从虚拟起点到合法点 i 的最小总代价 
 
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		b[i] = a[i] - i;
	}
	b[n + 1] = 1e9;   // 不一定所有最长不降子序列（LIS）的结尾都是 n
	// 为了所有非法段都能被处理到，加入一个所有 LIS 的结尾点 
	
	memset(mn_end, 0, sizeof(mn_end));
	int len = 0;     // mn_end 数组的当前长度 
	for (int i = 1; i <= n + 1; i ++) {
		int l = 0, r = len, p = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (mn_end[mid] <= b[i]) {
				p = mid;
				l = mid + 1;
			}
			else {
				r = mid - 1;
			}
		}
		if (p == len) {
			len ++;      // 更新全局 LIS 长度 
		} 
		mn_end[p + 1] = b[i];   // 长度为 p + 1 的 LIS 结尾最小值更新 
		// 如果 p + 2 也因为 i 可以被更新的更小，导致更新错误怎么办？
		// 答：不用担心
		// 假设后面有一个点 x，me[p + 1](new) < x < me[p + 2](new)
		// 并且 me[p + 2](old) < x < me[p + 3](old)
		// 这样会导致本应更新 p + 2 的 x 更新了 p + 3
		// 但很明显，不可能做到同时 < me[p + 2](new) 且 > me[p + 2](old)
		// 所以不用担心会更新错误 
		L[i] = p + 1;
		G[L[i]].push_back(i); 
	}
	
	cout << n - len + 1 << "\n";  // 不合法点的数量，因为多算了一个 n + 1 
	
	memset(dp, 0x7f, sizeof(dp));    // 初始化最大值 
	G[0].push_back(0);          // 添加虚拟起点 
	b[0] = -1e9; dp[0] = 0;    // 保证所有点都能接它后面     
	for (int j = 1; j <= n + 1; j ++) {
		for (int i : G[L[j] - 1]) if (i < j && b[i] <= b[j]){
			sumi[i] = 0;
			for (int k = i + 1; k < j; k ++) {
				sumi[k] = sumi[k - 1] + abs(b[k] - b[i]);
			}
			sumj[j] = 0;
			for (int k = j - 1; k > i; k --) {
				sumj[k] = sumj[k + 1] + abs(b[j] - b[k]);
			}
			
			for (int k = i; k < j; k ++) {
				dp[j] = min(dp[j], dp[i] + sumi[k] + sumj[k + 1]);
			} 
		}
	}
	cout << dp[n + 1] << "\n";
	
	return 0;
}

https://blog.csdn.net/tenkuo/article/details/153737588?spm=1001.2014.3001.5502