Description
现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。
但是不希望改变过多的数，也不希望改变的幅度太大。
Input
第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。n<=35000,保证所有数列是随机的
Output
第一行一个整数表示最少需要改变多少个数。 第二行一个整数，表示在改变的数最少的情况下，每个数改变
的绝对值之和的最小值。
Sample Input
4
5 2 3 5
Sample Output
1
4
Solution
神仙题目。
第一问考虑能保留下来多少，两个位置(i,j(i>j))，它们能保留下来当且仅当(a[i]-a[j]le i-j),移项得(a[i]-ile a[j]-j)。所以第一问构造一个新序列(b[i]=a[i]-i)，答案就是n-新序列最长不下降子序列。
第二问是神仙做法。对于任意({(i,j)|j<iwedge f[j]+1=f[i])})，显然只能改它们中间那一段使(b[i])不严格上升(因为保证了(f[j]+1=f[i]))，有个结论，一定是有一个分割点(k)，对于(xin [j,k])的(b[x]=b[j]),对于(xin [k+1, i])的(b[x]=b[i])。
可以感性的证明一下，假设我们现在有一种最优的修改方法，以(i)为横坐标，(b[i])为纵坐标，就可以得到几条阶梯状的线段（当前的修改方案），然后统计原(b[i])在线段上的点个数记为(up)，原(b[i])在线段下的点个数记为(down)，当一段线段上下(up=down)时，整条线段上移or下移都不会使答案更差，所以可以靠齐左边or右边。对于(up>down)的，可以让线段向下移动，(up<down)同理，向上移动，然后这样会使答案更优，成为更优的解法。所以最后的解法一定是这个结论里的摆法。（这个理解方法类似货场选址问题，大概是中位数相关）
上方的感性证明有人画了个gif动图：https://www.luogu.org/blog/costudy/solution-p2501
严谨一点的数学证明：https://www.luogu.org/blog/FlierKing/solution-p2501
然后具体实现上，枚举(i)，设(dp[i])表示以(i)结尾的(b)的非严格(LIS)长度，然后将(i)塞入(v[dp[i]])这个(vector)，对于每个(i)，遍历(vector)，设当前位置为(v[j])，选(b[p]<b[i])的点来转移。先处理出(|b[p]-b[k]|)和(|b[i]-b[k]|)的前缀和，然后可以枚举断点(k)，转移方程即为(f[i]=min {f[i],f[p]+sum1[k]+sum2[i]-sum2[k]})。因为题目中就保证了数列随机，然后因为随机数列的(LIS)长度期望是(log)的，所以复杂度是期望(O(n^2log n))的，里面有个(n)是跑不满的，所以实际上也跑的挺快的...主要还是数据随机才跑得动...
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 50010;
const ll inf = 1e10;
const int INTINF = 1e9;
int dp[N], n, a[N], b[N];
ll sum1[N], sum2[N];
vector<int> v[N];
ll f[N];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]), a[i] -= i;
a[++n] = INTINF;
dp[1] = 1; b[1] = a[1];
int len = 1;
for(int i = 2; i <= n; ++i) {
if(a[i] >= b[len]) b[++len] = a[i], dp[i] = len;
else {
int p = upper_bound(b + 1, b + len + 1, a[i]) - b;
b[p] = a[i]; dp[i] = p;
}
}
printf("%d
", n - len);
a[0] = -INTINF;
v[0].push_back(0);
for(int i = 1; i <= n; ++i) {
f[i] = inf;
for(int j = 0, Len = v[dp[i] - 1].size(); j < Len; ++j) {
int p = v[dp[i] - 1][j];
if(a[p] > a[i]) continue;
sum1[p - 1] = sum2[p - 1] = 0;
for(int k = p; k <= i; ++k) {
sum1[k] = sum1[k - 1] + abs(a[i] - a[k]);
sum2[k] = sum2[k - 1] + abs(a[p] - a[k]);
}
for(int k = p; k <= i; ++k) {
f[i] = min(f[i], f[p] + sum2[k] - sum2[p] + sum1[i] - sum1[k]);
}
}
v[dp[i]].push_back(i);
}
printf("%lld
", f[n]);
return 0;
}