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)。