排列

题目描述

比赛太下饭，硕硕吃撑了很生气。看着排行榜上WA的次数，拍着肚皮的硕硕就想留个作业。 参赛的每个学生都至少WA了一次，硕硕把每个学生WA的次数列了出来。现在硕硕想知道怎样去掉一些数字，可以让尽可能多的WA的次数对应在其排列的位置上。 硕硕：你们自己WA的次数，自己去处理吧🥧🍚。

输入格式

第一行为一个整数n，表示参赛人数。 接下来n个数，每个数分别代表参赛学生WA的次数。

输出格式

一个整数，表示去掉某些WA的次数后，最后剩下的数列中最多可以有多少个数在对应的位置上

样例输入

5 1 1 2 5 4

样例输出

3

提示

对于20%的数据，1<=n<=20 , 0<=ai<=1000; 对于60%的数据，1<=n<=100 , 0<=ai<=1000; 对于100%的数据，1<=n<=1000 , 0<=ai<=1000.

样例的解释： 一共有5个人，WA的次数分别为1, 1, 2, 5, 4 在去掉第2个人WA的次数后，数列为1, 2, 5, 4 其中的1, 2, 4三个数字是在其排列的位置上，所以答案为3

题解

看到这题首先想到的方法就是DP

首先定义一个数组 $DP[i][j]$ ，表示第$i$个数字，在第$j$个位置时的最优解是多少。 初始化所有元素值为0。

对于第$i$个数字，只有两种情况：取和不取。 如果取第$i$个数字，那么需要判断一下第$i$个数字是否是在第$j$个位置上，满足条件则用上一个数字的状态+1，不满足则直接赋值成上一个数字的状态。(上一个数字的状态为$DP[i-1][j-1]$) 如果不取第$i$个数字，直接把当前状态赋值成上一个数字在$j$位置的状态($DP[i-1][j]$)。

可得状态转移方程$DP[i][j]=Max(DP[i-1][j], DP[i-1][j-1] + (a[j]==j))$ 两者取最优解

以题中样例来说明：一共五个数：1 1 2 5 4：

• 当输入第一个数字 1 时： 判断1是否是第一个位置，$DP[1][1] = DP[0][0] + 1 = 1$。由于只输入了一个数字，所以只更新一个状态
• 当输入第二个数字 1 时： 判断1是否是第一个位置，根据状态转移方程，$DP[2][1]=DP[1][1] = 1$ 再判断1是否是第二个位置，根据状态转移方程，$DP[2][2]=DP[1][1]+0 = 1$
• 当输入第三个数字 2 时： 判断2是否是第一个位置，根据状态转移方程，$DP[3][1]=DP[2][1] = 1$ 再判断2是否是第二个位置，根据状态转移方程，$DP[3][2]=DP[2][1]+1 = 2$ 再判断2是否是第三个位置，根据状态转移方程，$DP[3][3]=DP[2][2]+0 = 1$
• 当输入第四个数字 5 时： 判断5是否是第一个位置，根据状态转移方程，$DP[4][1]=DP[3][1] = 1$ 再判断5是否是第二个位置，根据状态转移方程，$DP[4][2]=DP[3][2] = 2$ 再判断5是否是第三个位置，根据状态转移方程，$DP[4][3]=DP[3][2] + 0 = 2$ 再判断5是否是第四个位置，根据状态转移方程，$DP[4][4]=DP[3][3] + 0 = 1$
• 当输入第五个数字 4 时： 判断4是否是第一个位置，根据状态转移方程，$DP[5][1]=DP[4][1] = 1$ 再判断4是否是第二个位置，根据状态转移方程，$DP[5][2]=DP[4][2] = 2$ 再判断4是否是第三个位置，根据状态转移方程，$DP[5][3]=DP[4][2] + 0 = 2$ 再判断4是否是第四个位置，根据状态转移方程，$DP[5][4]=DP[4][3] + 1 = 3$ 再判断4是否是第五个位置，根据状态转移方程，$DP[5][5]=DP[4][4] + 0 = 1$

数字\位置	1	2	3	4	5
$a[1]$: 1	1	0	0	0	0
$a[2]$: 1	1	1	0	0	0
$a[3]$: 2	1	2	1	0	0
$a[4]$: 5	1	2	2	1	0
$a[5]$: 4	1	2	2	3	1

代码：

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int a[1010], dp[1010][1010];

int main()
{
    int n;
    cin>>n;

    for(int i = 1; i <= n; i++)
    {
        cin>>a[i];
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + (a[i] == j));
            ans = max(ans, dp[i][j]);
        }
    }

    cout<<ans;
    return 0;
}

优化：

根据DP的更新过程可以看出，当前状态只与上一个数字的状态有关，所以可以尝试将二维数组优化为一维数组。