题目链接


  • 设计状态:$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\])$。
    • *

代码

    #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 14th, 2020 at 08:44 pm