题目链接 Sonya and Problem Wihtout a Legend
题意 给定一个长度为n的序列，你可以对每个元素进行$+1$或$-1$的操作，每次操作代价为$1$。
求把原序列变成严格递增子序列的所需最小花费。
考虑$DP$。
首先比较常见的套路就是把每个$a[i]$减去$i$，然后把这个新的序列升序排序，记为$b[i]$。
这里有个结论：最后操作完成之后的每个数都是$b[i]$中的某个数。
然后就可以$DP$了，令$f[i][j]$为前$i$个数操作之后每个数都小于等于$b[j]$的最小花费。
则有\begin{equation*}f[i][1] = \sum_{i=1}^nabs(a[i] - b[1])\end{equation*}
$f[i][j] = min(f[i][j - 1], f[i - 1][j] + abs(a[i] - b[j]))$
时间复杂度$O(nlogn + n^{2})$
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define MP make_pair
#define fi first
#define se second typedef long long LL; const int N = 3010; int n;
LL a[N], b[N], f[N][N];
LL ret, ans; int main(){ scanf("%d", &n);
rep(i, 1, n) scanf("%lld", a + i), a[i] -= i, b[i] = a[i];
sort(b + 1, b + n + 1); rep(i, 0, n + 1) rep(j, 0, n + 1) f[i][j] = 1e18;
rep(i, 0, n + 1) f[0][i] = 0; rep(i, 1, n) f[i][1] = f[i - 1][1] + abs(a[i] - b[1]); rep(i, 1, n){
rep(j, 1, n){
f[i][j] = min(f[i][j - 1], f[i - 1][j] + abs(a[i] - b[j]));
}
} printf("%lld\n", f[n][n]);
return 0;
}