记录一个比较有意思的题目
题意： 给一个数组 a 从数组中删除一个元素的时候，后面的元素会自动前移。问最少删除多少元素可以使得数组中 a[i]==i 的元素数量>=k；
做法： 考虑 dp dp[i][j]代表前i个元素删除 j 个时的满足条件的数量 。转移分删除当前i元素和不删 分别是 dp[i-1][j-1] 和 dp[i-1][j] + (a[i]==i-j) 取最大值
代码 ：
ll dp[2005][2005]; ll n,k; ll a[2005]; void solve(){ cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; }for(int i=1;i<=n;i++){ for(int j=0;j<=i;j++){ dp[i][j]=max(dp[i-1][j-1],dp[i-1][j]+(a[i]==i-j)); } } ll ans=-1; for(int i=0;i<=n;i++){ if(dp[n][i]>=k){ ans=i; break; } } cout<<ans<<endl; }