题解 P1799 【数列】

· · 题解

由于是删数类型的动态规划，所以很容易想到：

dp{_i}{_j} 表示前 i 个数中删去 j 个数后，原来处于前 i 个数当中的数所能满足 a_i=i 的 i 的个数的最大值。

这样，显然有 0 \le j \le i 。
那么状态转移方程怎么推呢？

  1. 如果从 dp_{i-1}{_{j-1}} 来推的话，可以保证第 i 个数一定被删，这样答案仍为 dp_{i-1}{_{j-1}} ；
  2. 如果从 dp_{i-1}{_j} 来推的话，第 i 个数就没有被删掉，结果为 dp_{i-1}{_j}，这时原来的第 i 个数处于第 i-j 个位置，如果满足 a_i=i-j ，答案就可以 +1 。

综上， dp{_i}{_j}=\left\{ \begin{aligned} &dp_{i-1}{_{j-1}} \\ &dp_{i-1}{_j} \ +\ (a_i==i-j) \\ \end{aligned} \right.

最后答案为 \max\nolimits_{i=1}^{n}\max\nolimits_{j=0}^{i} dp_i{_j} ，即所有 dp 值的最大值。

代码如下：

#include <cstdio>
using namespace std;
int n,ans;
int a[1005];
int dp[1005][1005];
inline int max(int a,int b){
    return a>b?a:b;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for (int i=1;i<=n;i++){
        for (int j=0;j<=i;j++){
            if (j>0) dp[i][j]=dp[i-1][j-1];\\注意j=0时j-1会越界
            dp[i][j]=max(dp[i][j],dp[i-1][j]+(a[i]==i-j));\\如上所示的状态转移方程
            ans=max(ans,dp[i][j]);\\如上所示的答案
        }
    }
    printf("%d",ans);
    return 0;
}

这里有AC代码哦，但我相信你不会抄题解的！