题目大意：
给你一个序列，让你把它变成一个严格递增的序列。
对每个数字，无论+1或者-1都消耗1，问你把它变成严格递增的序列的最小cost
解题思路：
DP
首先根据题目，a[i+1] >= a[i] + 1，两边同时减去i+1，就得到a[i+1] - (i + 1) >= a[i] - i
设b[i] = a[i] - i，则b序列是不降序列，那么问题就变成了将序列变成一个不降序列所需要的花费
设dp[i][j]表示将第i个元素变成j的最小cost，那么状态转移方程就是dp[i][j] = min(dp[i-1][k]) + abs(a[i] - j);
但是显然这样是过不去的。时间负责度过高。O(n^3)
我们可以发现，min(dp[i-1][k])其实就是上一个元素的最优解，可以用一个数组解决，负责度变成O(n^2)
但是还是不行。关键在于j是一个具体的数字，范围是1-1e9.
根据经验，我们知道，需要离散化处理。但是怎么离散化呢= =这点我还没考虑好，所以先存这里。
最终的状态转移：
dp[i][j] = f[j] + abs(a[i] - b[j]);
代码：
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define mp make_pair
#define pb push_back
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define fun(x) ((x) >= 0 ? (x) : -(x))
typedef long long LL;
typedef pair<int, int> pi;
const int maxn = 3005;
const LL inf = 1e18 + 5;
LL a[maxn], b[maxn], f[maxn], dp[maxn][maxn];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
a[i] = a[i] - i;
b[i] = a[i];
}
sort(b + 1, b + n + 1);
fill(f, f + n + 1, inf);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
dp[i][j] = (i == 1 ? 0 : f[j]) + fun(a[i] - b[j]);
f[j] = min(f[j - 1], dp[i][j]);
//cout << f[j] << endl;
}
}
cout << f[n] << endl;
//system("pause");
return 0;
}</span>