CF946G Almost Increasing Array 题解

题目传送门

前置知识

最长不下降子序列 | 权值树状数组及应用

解法

若将 \(\{ 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;
}