题解 | #Sequence Game#

题目链接

题目描述

由于你帮助 Alice 回答得非常好，Sept 又找到了 Bob，希望能难倒他。
他给了要求 Bob 组成一个长度为 n 的新的数列 a，其中数列 a 的每一个元素 ​都有 k 个取值。
求所有可能的数列 a 中的最长上升子序列的最大长度。
由于 Sept 怕题目钛难，所以他答应 Bob，对于每个 i，k 个取值不降。

输入描述

第一行两个数 k,n,意义如题述。
接下来 n 行，每行 k 个数，即 的 k 个取值。

输出描述

仅一行一个整数，即所有可能的数列 a 中的最长上升子序列的最大长度。

示例输入

2 2
1 3
1 2

示例输出

2

思路

"最长上升子序列长度",从题目描述中捕捉到这几个词,DNA就动了!
我们很自然地会从最长上升子序列解题方向考虑这道题。
但由题目我们可知,这n个数都有k个可能的取值，
也就是说，这n个数的具体取值是待定的，所以我们无法通过直接套用最长上升子序列的解题模板解题。

从动态规划的思想出发，我们很容易想到的思路便是枚举每一个的取值，进行动态规划。如下代码所示：

f[i][j] = 0
# f[i][j] 表示以a[i][j]结尾的最长上升子序列长度
for i in range(n):
    for j in range(k):
        for p in range(i):
            for q in range(k):
                if A[i][j] > A[p][q]:
                    f[i][j] = max(f[i][j],f[p][q] + 1)

思路是对的，但四层循环，对于的数量级，毫无疑问会超时。
每一个就占据数组的一个维度，n个便是二维数组.
对于这种二维数组,我们遇到的一个困难便是难以使用的上升子序列算法,而只能使用基于朴素最长上升子序列的复杂度为算法。

因此，我们需要考虑是否能将二维数组降到一维，如何降维？

因为“对于每一个i，k个值不降”，如果将每一行以从大到小存入一个一维数组，
例如对于样例输入，a = [3,1,2,1]，那么对于任意一个上升子序列，至多只会取到的一个值（可以用反证法证得）。

于是，问题转变为如何从一个以为数组中求最长上升子序列长度了。
套用一个复杂度为O(nlogn)的算法即可。

代码

python3

k,n = map(int,input().split())
A = []
for i in range(n):
    T =  list(map(int,input().split()))
    T.reverse()
    A += T

ln = 0
f = [0] * (len(A) + 1)
f[0] = int(-2e9)
for i in range(len(A)):
    l = 0
    r = ln
    while l < r:
        mid = l + r + 1 >> 1
        if f[mid] >= A[i]: r = mid - 1
        else: l = mid
    f[r + 1] = A[i]
    ln = max(ln,r + 1)
print(ln) 

C++

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010, M = 5000 * 1000 + 10;
int f[N];
int A[M];
int main(){
    int n,k;
    scanf("%d%d",&k,&n);
    for(int i = 0;i < n;i++){
        for(int j = k - 1;j >= 0;j--){
            scanf("%d",&A[i * k + j]);
        }
    }
    // LIS
    int len = 0;
    f[0] = -2e9;
    for(int i = 0,m = k * n;i < m;i++){
        int l = 0,r = len;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(f[mid] >= A[i]) r = mid - 1;
            else l = mid;
        }
        f[r + 1] = A[i];
        len = max(len,r + 1);
    }
    printf("%d\n",len);
    return 0;
}

ps

• 存储长度为i的上升子序列的第i个数（该数为所有可能的取值中的最小值）
• 使用python代码实现本题仍会有超时（超过2000ms）的情况，使用C++（280ms）实现不会出现此问题。对于python效率问题，我暂时想不到如何从算法上或者代码上做进一步提升——不过如果用PyPy代替Python进行编译。
• 对题意做好理解再解题。题目让我迷惑了好久