给定一个长度为 n ( n ≤ 3000 ) n \pod {n \le 3000} n(n≤3000) 的数组，可以花费 1 1 1 的代价将任意元素加 1 1 1 或者减 1 1 1。问将整个数组变得单调递增的最小代价。
出题人的正解是 O ( n 2 ) O(n^2) O(n2) 的动态规划。这里有 O ( n log n ) O(n \log n) O(nlogn) 的做法（来源）：
我们先用一个套路把严格单调递增变成非严格单调递增：只需要令 a i = a i − i a_i = a_i - i ai=ai−i 即可。设 f i ( x ) f_i(x) fi(x) 表示使得前 i i i 个数满足单调不递减的条件并且第 i i i 个数不超过为 x x x 的最小代价，有状态转移方程：
f i ( x ) = { min y ≤ x { ∣ a i − Y ∣ } i = 1 min y ≤ x { f i − 1 ( Y ) + ∣ a i − Y ∣ } otherwise f_i(x) = \begin{cases} \min_{y \le x} \{ |a_i - Y| \} & i = 1 \\ \min_{y \le x} \{ f_{i - 1}(Y) + |a_i - Y| \} & \text{otherwise} \end{cases} fi(x)={miny≤x{∣ai−Y∣}miny≤x{fi−1(Y)+∣ai−Y∣}i=1otherwise
可以发现， f i ( x ) f_i(x) fi(x) 是一个单峰函数：感性理解下，当 x x x 很小时，要把前面所有数都变得很小，代价就很大，当 x x x 很大时，把 a i a_i ai 变成 x x x 的代价也越来越多。
我们设当 f i ( x ) f_i(x) fi(x) 取得最小值的 x x x 为 x i x_i xi。显然可以根据 x i x_i xi 的大小分为两种情况：
我们设直角坐标系 x O y xOy xOy，其中 y = f i ( x ) y = f_i(x) y=fi(x)。我们仔细分析下这个图应该长什么样的：
（图为示意图）
斜率为 0 0 0 的直线的前面的直线的斜率一定递减，为什么呢？因为随着我们 x x x 的减小，前面需要修改的数也就越来越多。而斜率为 0 0 0 的直线的后面只有一条斜率为 1 1 1 的直线，相当于我们只修改了 a i a_i ai。
我们考虑转移的意义。对于在后面新加入的一个数 a i a_i ai， a i a_i ai 对总代价的贡献显然为 y = ∣ x i − a i ∣ y = |x_i - a_i| y=∣xi−ai∣：
而转移后的函数图像显然是状态转移方程的图像。
上图对应情况 1 1 1，即 a i ≥ x i a_i \ge x_i ai≥xi（ x i x_i xi 为斜率为 0 0 0 的最左点），那么显然，转移后，图像的最低点为 x = a i x = a_i x=ai 处。因此我们有结论 x i = a i x_i = a_i xi=ai。另外，很显然的是，对于原函数图像我们不需要斜率大于 0 0 0 的部分，因为这样转移一定不优。
下面让我们看看如何分析情况 2 2 2。
观察发现，我们无论如何也不可能选择让 a i a_i ai 变小（不管是从逻辑上还是从图形上都很显然），继续观察发现，当 x = a i − 1 x = a_{i - 1} x=ai−1 时， f i ( x ) f_i(x) fi(x) 有最小值 f i − 1 ( x i − 1 ) + ( x i − 1 − a i ) f_{i - 1}(x_{i - 1}) + (x_{i - 1} - a_i) fi−1(xi−1)+(xi−1−ai)。
显然的是， f x n f_{x_n} fxn 就是原问题的答案。如果我们能够维护函数图像，问题就解决了。
根据前面的分析，我们有一个新的状态转移方程：
f i ( x i ) = { f i − 1 ( x i − 1 ) a i ≥ x i − 1 f i − 1 ( x i − 1 ) + ( x i − 1 − a i ) a i < x i − 1 f_i(x_i) = \begin{cases} f_{i - 1}(x_{i - 1}) & a_i \ge x_{i - 1} \\ f_{i - 1}(x_{i - 1}) + (x_{i - 1} - a_i) & a_i < x_{i - 1} \end{cases} fi(xi)={fi−1(xi−1)fi−1(xi−1)+(xi−1−ai)ai≥xi−1ai<xi−1
换句话说，我们的答案为 x i − 1 − a i x_{i - 1} - a_i xi−1−ai 的和。也就是说我们可以仅仅维护 x i − 1 x_{i - 1} xi−1 就达到计算答案的目的。
前面，我们仅仅解决了最优解在哪里的问题，那么剩下部分的图像是怎样的呢？
当 a i ≥ x i − 1 a_i \ge x_{i - 1} ai≥xi−1 时，显然，将不会存在斜率为 0 0 0 的直线。每一个关键点（ x = x i x = x_i x=xi 的点为关键点）的斜率都会加 1 1 1。（想一想，为什么）
当 a i < x i − 1 a_i < x_{i - 1} ai<xi−1 时， a i a_i ai 之后的直线的斜率减 1 1 1，之前的斜率加 1 1 1，因此仍然满足斜率递增的性质，但是由于后面的斜率会加 1 1 1，一定会导致恰好一条斜率为 1 1 1 的直线出现，我们删除它即可。细节留给你们思考。
用大根堆来维护关键点的横坐标。具体实现时，我们不需要保存斜率为 0 0 0 的直线，也就是说要把前面我说的大于 0 0 0 改成大于等于 0 0 0。
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
putchar('\n');
}
const int maxn = 3005;
int n;
int a[maxn];
void run()
{
n = readIn();
for (int i = 1; i <= n; i++)
a[i] = readIn();
LL ans = 0;
std::priority_queue<int> q;
for (int i = 1; i <= n; i++)
{
int& x = a[i];
x -= i;
q.push(x);
if (q.size() && q.top() > x)
{
ans += q.top() - x;
q.pop();
q.push(x);
}
}
printOut(ans);
}
int main()
{
run();
return 0;
}