推推式子，对于原数列 $a[i],a[j]$ 如果要保留它们，那么它们之间的数就要改成单调上升
显然能改成单调上升的条件是 $a[i]<a[j]$ 并且 $a[j]-a[i]>=j-i$ ，也就是 $a[j]-j>=a[i]-i$
所以设 $b[i]=a[i]-i$，那么对于第一问就只要求 $b[i]$ 的最长不下降子序列长度就是最多可以保留的数的个数
然后考虑第二个问题，对于 $b[i],b[j]$，如果它们处于最长不降子序列中相邻的两个位置，那么说明它们之间的数权值 $ otin [b[i],b[j]]$
然后发现合法的修改有很多种，试着推一下结论，然后发现把 $b[i],b[j]$ 之间修改的最优方案一定是左边一段全改成 $b[i]$，右边一段全改成 $b[j]$
考虑证明一下，假设某种最优方案中间有一段不在 $b[i]$ 或者 $b[j]$，对这一段位置中小于 $b[i]$ 的和大于 $b[j]$ 数的个数分类讨论一下
设这一段有 $x$ 个小于 $b[i]$ 的位置，$y$ 个大于 $b[j]$ 的位置
如果 $x<y$ ，那么把这一段整体改成 $b[j]$ ，代价改变量为 $Delta valcdot (x-y)$，显然代价更小
同理 $x>y$ ，那么把区间整体改成 $b[i]$，代价改变量为 $Delta valcdot (y-x)$，同样代价减小
如果 $x=y$ ，那么把区间移动不会影响答案的最优性
综上所述，最优的方案一定包括：左边一段全改成 $b[i]$，右边一段全改成 $b[j]$
然后直接枚举分界点 $k$ 转移即可，具体就是设 $g[i]$ 表示前 $i$ 位合法时，第 $i$ 位不修改的最优方案，那么有
$g[i]=g[j]+w$，其中 $i,j$ 满足 $f[i]=f[j]+1$ ，$w$ 随着 $k$ 而改变，直接 $vector$ 维护之前每个 $f$ 值的所有 $j$ 即可
因为数据随机所以不会 $T$ 飞，具体实现看代码
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7,INF=1e9; int n,a[N],b[N],d[N],c[N]; int f[N],t[N],Mx; inline void add(int x,int v) { while(x<=n) t[x]=max(t[x],v),x+=x&-x; } inline int ask(int x) { int res=0; while(x) res=max(res,t[x]),x-=x&-x; return res; } ll sum[N],g[N]; vector <int> V[N]; int main() { n=read(); for(int i=1;i<=n;i++) { a[i]=read(); b[i]=a[i]-i; c[i]=d[i]=b[i]; sum[i]+=b[i]; } sort(d+1,d+n+1); for(int i=1;i<=n;i++) b[i]=lower_bound(d+1,d+n+1,b[i])-d;//离散化 for(int i=1;i<=n;i++) { f[i]=ask(b[i])+1,add(b[i],f[i]); Mx=max(Mx,f[i]); } ll Sl=0,Sr=0,Ans; V[0].push_back(0); c[0]=-INF;//注意边界条件 memset(g,0x3f,sizeof(g)); Ans=g[0]; g[0]=0;//初始化 for(int i=1;i<=n;i++) { int len=V[f[i]-1].size(); for(int j=0;j<len;j++) { int &p=V[f[i]-1][j]; Sl=Sr=0;//Sl维护当前[p+1,k-1]都改成c[p]的代价,Sr维护当前[k,i]都改成c[i]的代价 if(b[p]>b[i]) continue; for(int k=p+1;k<i;k++) Sr+=abs(c[i]-c[k]); for(int k=p+1;k<=i;k++) { g[i]=min(g[i],g[p]+Sl+Sr); Sl+=abs(c[p]-c[k]); Sr-=abs(c[i]-c[k]); } } V[f[i]].push_back(i); if(f[i]==Mx)//更新答案 { Sl=0; for(int j=i+1;j<=n;j++) Sl+=abs(c[i]-c[j]); Ans=min(Ans,g[i]+Sl); } } printf("%d %lld ",n-Mx,Ans); return 0; }