自动搬运

查看原文

来自洛谷，原作者为

	muyang_233 enfj|阔耐的蓝孩纸|MOer/OIer

搬运于2025-08-24 21:30:28，当前版本为作者最后更新于2020-07-26 17:38:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

$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代码哦，但我相信你不会抄题解的！