我们分别考虑一二问。
对于第一问，我们思考一个子序列是合法的「不用修改」的子序列的充要条件。
容易想到的，这个条件是：
$$ \forall i,j\in S, i=j-i$$
自然语言化地说，就是，对于这个不用修改的子序列中的任意两个元素，它们的值的差距至少要大于它们间的元素个数，这样才能放得下它们中间的元素。
移项，我们得到：
$$a_j-j>=a_i-i$$
所以，我们令\(b_i=a_i-i\)，那么第一问中不用修改的个数就是\(b\)的最长不下降子序列长度。
对于第二问，首先，它可以被转化为「最小修改代价求\(b\)单调不减」。
我们有一个结论：相邻两关键点\(i,j\)间一定可以找到一条分界线，使得线左端的所有点变化成\(b_i\)，右端所有点变化成\(b_j\)会最优。
这是如何证明的呢？
首先，我们知道，\(i,j\)之间的任意一个点，它的值必然要小于\(b_i\)或者大于\(b_j\)，否则选取这个点只会让答案更优。
然后，我们尝试进行反证。如果有一个点修改以后位于中间，并且它可以被修改到某一边，那么显然修改到某一边之后答案会更小。
如果将分界线定在某处，会使得某些点与它们的最优处于的边不相同，那么考虑这些点与分界点之间的其他点的数量。
如果其他点的数量小于这些点，那么不妨把这些点修改后的位置换到另一边，这样答案就变小了点数差*上下两边距离。
否则，不如不修改。
所以我们证明了这个结论。
然后是关于时间复杂度的。可以证明，在序列随机的情况下，最长不下降子序列的期望长度是logn级别的。（我不会证，也找不到文章。求大佬教教我）
注意：要提前把\(b_0\)设成\(-INF\)，并在末尾插入一个\(INF\)的点。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=35005;
const int INF=0x3f3f3f3f;
inline ll Abs(ll X){
return X>=0?X:-X;
}
inline ll Min(ll A,ll B){
return A<B?A:B;
}
int n,a[N],b[N],nm[N];
ll f[N],sm1[N],sm2[N];
struct ee{
int v;
int nxt;
}e[N];
int h[N],et=0;
inline void add(int U,int V){
e[++et]=(ee){V,h[U]};
h[U]=et;
}
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
b[i]=a[i]-i;
}
int cnt=0,nw;
b[0]=-INF;f[0]=-INF;
b[++n]=INF;
for(int i=1;i<=n;++i){
if(b[i]>=f[cnt]){
f[++cnt]=b[i];
nm[i]=cnt;
}else{
nw=upper_bound(f+1,f+cnt,b[i])-f;
f[nw]=b[i];
nm[i]=nw;
}
}
printf("%d\n",n-cnt);
for(int i=n;i>=0;--i){
add(nm[i],i);
f[i]=INF;
}
f[0]=0;
int v;
for(int i=1;i<=n;++i){
for(int j=h[nm[i]-1];j;j=e[j].nxt){
v=e[j].v;
if(v>i||b[v]>b[i]){
continue;
}
sm1[v]=0;
for(int k=v+1;k<=i;++k){
sm1[k]=sm1[k-1]+Abs(b[k]-b[v]);
}
sm2[i-1]=0;
for(int k=i-2;k>=v;--k){
sm2[k]=sm2[k+1]+Abs(b[k+1]-b[i]);
}
for(int k=v;k<i;++k){
f[i]=Min(f[i],f[v]+sm1[k]+sm2[k]);
}
}
}
printf("%lld\n",f[n]);
}
int main(){
init();
return 0;
}