前置知识
解法
若将 \(\{ a \}\) 变成严格递增序列，至少需要更改 \(n\) 减去 \(\{ a_{i}-i \}\) 的最长不下降子序列长度个数。
- 证明
- 对于 \(a_{i},a_{j}(i<j)\) 若都在最终的严格递增序列里，则有 \(a_{i}-a_{j} \le i-j\)，即 \(a_{i}-i \le a_{j}-j\)。而这 \(\{ a_{i}-i \}\) 的最长不下降子序列长度个数是不需要更改的。
考虑计算最多能保留的数的个数。
令 \(\forall i \in [1,n],b_{i}=a_{i}-i\)。
设 \(f_{i,0/1}\) 表示以 \(i\) 结尾的前缀中没有/有删除过的数时（删除的这个数仅能 \(\in [1,i-1]\)，能够在最终保留但不参与运算）最多能保留的数的个数，状态转移方程为 \(\begin{cases} f_{i,0}=\max\limits_{j=1}^{i-1} \{ [b_{j} \le b_{i}] \times (f_{j,0}+1) \} \\ f_{i,1}=\max(\max\limits_{j=1}^{i-1} \{ [b_{j} \le b_{i}] \times (f_{j,1}+1) \},\max\limits_{j=1}^{i-2} \{ [b_{j} \le b_{i}+1] \times (f_{j,0}+1) \}) \end{cases}\)，边界为 \(\begin{cases} f_{1,0}=1 \\ f_{1,1}=0 \end{cases}\)。
权值树状数组优化 DP 即可。
最终，有 \(max(n-\max\limits_{i=1}^{n} \{ f_{i,0},f_{i,1} \},0)\) 即为所求。
- 使用删除一定比不使用删除不劣。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
ll a[200010],b[200010],c[400010],f[200010][2];
struct BIT
{
ll c[400010];
ll lowbit(ll x)
{
return (x&(-x));
}
void add(ll n,ll x,ll val)
{
for(ll i=x;i<=n;i+=lowbit(i))
{
c[i]=max(c[i],val);
}
}
ll getsum(ll x)
{
ll ans=0;
for(ll i=x;i>=1;i-=lowbit(i))
{
ans=max(ans,c[i]);
}
return ans;
}
}T[3];
int main()
{
ll n,ans=0,i;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i]-i;
c[2*i-1]=b[i];
c[2*i]=b[i]+1;
}
sort(c+1,c+2*n+1);
c[0]=unique(c+1,c+2*n+1)-(c+1);
for(i=1;i<=n;i++)
{
f[i][0]=T[0].getsum(lower_bound(c+1,c+1+c[0],b[i])-c)+1;
f[i][1]=T[1].getsum(lower_bound(c+1,c+1+c[0],b[i])-c);
f[i][1]+=(f[i][1]!=0);
if(i-2>=1)
{
f[i][1]=max(f[i][1],T[2].getsum(lower_bound(c+1,c+1+c[0],b[i]+1)-c)+1);
}
T[0].add(c[0],lower_bound(c+1,c+1+c[0],b[i])-c,f[i][0]);
T[1].add(c[0],lower_bound(c+1,c+1+c[0],b[i])-c,f[i][1]);
if(i-1>=1)
{
T[2].add(c[0],lower_bound(c+1,c+1+c[0],b[i-1])-c,f[i-1][0]);
}
}
for(i=1;i<=n;i++)
{
ans=max(ans,max(f[i][0],f[i][1]));
}
cout<<max(n-1-ans,0ll)<<endl;
return 0;
}