描述 某学校有三个班,每个班N个同学 每个同学都有一个身高值 现在希望从每个班选出一个同学出来,并且满足 此三人的身高是严格上升的。问有多少种选法 格式输入 第一行给出数字N 接下来三行,每行给出N个数字,其权值<=1e9 N<=1e5
时间: 2024-05-20 22:12:59 浏览: 21
这道题可以使用动态规划来解决。具体来说,可以定义一个三维的状态数组 $dp[i][j][k]$,表示选到第 $i$ 个班,第一个人的身高为 $j$,第二个人的身高为 $k$ 时,满足条件的选法数。
初始状态为 $dp[0][0][0]=1$,表示还没有选到任何一个班时,有一种选法。
然后,对于每个班的同学身高值,可以依次更新状态数组。具体来说,对于第 $i$ 个班的同学身高值 $h$,可以枚举前两个人的身高值 $j$ 和 $k$,如果 $h>j$ 且 $h>k$,则可以更新状态数组:
$$
dp[i][h][k] += dp[i-1][j][k] \\
dp[i][j][h] += dp[i-1][j][k] \\
dp[i][h][j] += dp[i-1][j][k]
$$
其中,第一个式子表示当前选的同学身高值为 $h$,且前两个人身高值为 $j$ 和 $k$,这种情况的选法数。第二个式子和第三个式子分别表示当前选的同学身高值为 $h$,且前两个人身高值为 $j$ 和 $k$ 的两种情况的选法数。
最终,所求的答案为 $dp[3][j][k]$ 的所有 $(j,k)$ 的和。
时间复杂度为 $O(N^3)$。
相关问题
二分法,某学校有1、2、3共三个班,每个班有N个同学 每个同学都有一个身高值 现在希望分别从1、2、3班选出一个同学出来,并且满足 此三人的身高是严格上升的。 问有多少种选法?
我们可以用动态规划来解决这个问题。首先,我们将每个班的同学按照身高从小到大排序。然后,我们定义一个三维数组 $dp[i][j][k]$,表示从第一个班中选取身高为 $i$ 的同学,从第二个班中选取身高为 $j$ 的同学,从第三个班中选取身高为 $k$ 的同学,且满足身高是严格上升的方案数。我们可以使用如下递推式:
$$ dp[i][j][k] = \sum_{p<i,q<j,r<k}dp[p][q][r] $$
其中,$p<i,q<j,r<k$ 且三个同学的身高是按照严格上升的顺序排列的。递推的边界条件为 $dp[i][j][k]=1$,当且仅当 $i=j=k=1$ 时成立。最终答案为 $\sum_{i=1}^{N}\sum_{j=1}^{N}\sum_{k=1}^{N}dp[i][j][k]$。
时间复杂度为 $O(N^3\log N)$,其中 $\log N$ 是排序的复杂度。
Description 某学校有三个班,每个班N个同学 每个同学都有一个身高值 现在希望从每个班选出一个同学出来,并且满足 此三人的身高是严格上升的。 问有多少种选法 Format Input 第一行给出数字N 接下来三行,每行给出N个数字,其权值<=1e9 N<=1e5
这是一个典型的动态规划问题。我们可以用 dp[i][0/1/2] 表示选到第 i 个人时,分别以第 i 个人为结尾,第 i 个人和第 i-1 个人为结尾,第 i 个人、第 i-1 个人和第 i-2 个人为结尾的严格上升子序列的个数。其中 0/1/2 分别表示以第 i 个人/第 i-1 个人/第 i-2 个人为结尾。
根据定义,我们可以得到转移方程:
- dp[i][0] = max(dp[j][0]) + 1, j < i 且 h[j] < h[i],表示以第 i 个人为结尾的上升子序列个数为前面所有以身高小于第 i 个人的同学结尾的上升子序列个数的最大值加 1。
- dp[i][1] = max(dp[j][0]) + 1, j < i 且 h[j] < h[i],表示以第 i-1 个人和第 i 个人为结尾的上升子序列个数为前面所有以身高小于第 i 个人的同学结尾的上升子序列个数的最大值加 1。
- dp[i][2] = max(dp[j][1]) + 1, j < i 且 h[j] < h[i],表示以第 i-2 个人、第 i-1 个人和第 i 个人为结尾的上升子序列个数为前面所有以身高小于第 i 个人的同学结尾的上升子序列个数的最大值加 1。
最终结果即为 dp[N][2],即所有同学均选出的情况下,以任意同学为结尾的上升子序列个数。
时间复杂度为 O(N^2)。可以通过状态压缩优化空间复杂度到 O(N)。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)