Loading... [题目链接](https://www.luogu.org/problemnew/show/P1799 "题目链接") <!--more--> * * * * 设计状态:$f\[i\]\[j\]$表示在前i个数字当中，删掉j个能得到符合$a_i=i$情况的最大值。 * 设计状态转移: 1. 如果要删第$i$个，$f\[i\]\[j\]=f\[i-1\]\[j-1\]$ 2. 如果不删第$i$个： 1. 如果$a\_i=i-j$(前面删掉$j$个刚好使$a\_i$满足条件)，$f\[i\]\[j\]=max(f\[i\]\[j\],f\[i-1\]\[j\]+1)$。 2. 否则，$f\[i\]\[j\]=max(f\[i\]\[j\],f\[i-1\]\[j\])$。 * * * #### 代码 ```cpp #include<bits/stdc++.h> using namespace std; int n,a[1009],f[1009][1009]; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ if(a[i]==i) f[i][0]=f[i-1][0]+1; else f[i][0]=f[i-1][0]; } for(int i=1;i<=n;i++){ for(int j=0;j<i;j++){ f[i][j]=f[i-1][j-1]; if(a[i]!=i-j) f[i][j]=max(f[i][j],f[i-1][j]); else f[i][j]=max(f[i][j],f[i-1][j]+1); } } int maxn=0; for(int i=1;i<n;i++){ maxn=max(maxn,f[n][i]); } cout<<maxn; return 0; } ``` Last modification：March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏