272. 最长公共上升子序列

Powered by:NEFU AB-IN

Link

272. 最长公共上升子序列

• 题意

如题

• 思路

若按这个思路的话，代码为$O(n^3)$

for (int i = 1; i <= n; i ++ )
{
    for (int j = 1; j <= n; j ++ )
    {
        f[i][j] = f[i - 1][j];
        if (a[i] == b[j])
        {
            int maxv = 1;
            for (int k = 1; k < j; k ++ )
                if (b[i] > b[k])
                    maxv = max(maxv, f[i - 1][k] + 1);
            f[i][j] = max(f[i][j], maxv);
        }
    }
}

然后我们发现，b[i] > b[k] 中的 b[i] 可以替换为 a[i]，也就是求比a[i]小的b[k]的值有什么，这个地方就会被重复计算，因为a[i]是固定的，b中比a[i]小的值也是固定的
所以设置maxv是满足a[i] > b[k]的f[i - 1][k] + 1的 前缀最大值
也就是 if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j]);
因此可以直接将maxv提到第一层循环外面，减少重复计算，此时只剩下两重循环。

最终答案枚举子序列结尾取最大值即可。

• 代码

'''
Author: NEFU AB-IN
Date: 2024-07-03 20:45:57
FilePath: \Acwing\272\272.py
LastEditTime: 2024-07-03 22:35:46
'''
# 3.8.19 import
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, fabs, floor, gcd, log, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin, stdout
from typing import Any, Dict, Generic, List, TypeVar, Union

TYPE = TypeVar('TYPE')

# Data structure


class SA(Generic[TYPE]):
    def __init__(self, x: TYPE, y: TYPE):
        self.x = x
        self.y = y

    def __lt__(self, other: 'SA[TYPE]') -> bool:
        return self.x < other.x

    def __eq__(self, other: 'SA[TYPE]') -> bool:
        return self.x == other.x and self.y == other.y

    def __repr__(self) -> str:
        return f'SA(x={self.x}, y={self.y})'


# Constants
N = int(2e5 + 10)  # If using AR, modify accordingly
M = int(20)  # If using AR, modify accordingly
INF = int(2e9)
OFFSET = int(100)

# Set recursion limit
setrecursionlimit(INF)

# Read


def input(): return stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
def read(): return map(int, input().split())
def read_list(): return list(read())


# Func
class std:
    letter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)  # A -> 0
    num_to_letter = staticmethod(lambda x: ascii_uppercase[x])  # 0 -> A
    array = staticmethod(lambda x=0, size=N: [x] * size)
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [std.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)
    removeprefix = staticmethod(lambda s, prefix: s[len(prefix):] if s.startswith(prefix) else s)
    removesuffix = staticmethod(lambda s, suffix: s[:-len(suffix)] if s.endswith(suffix) else s)

    @staticmethod
    def find(container: Union[List[TYPE], str], value: TYPE):
        """Returns the index of value in container or -1 if value is not found."""
        if isinstance(container, list):
            try:
                return container.index(value)
            except ValueError:
                return -1
        elif isinstance(container, str):
            return container.find(value)

    @staticmethod
    def pairwise(iterable):
        """Return successive overlapping pairs taken from the input iterable."""
        a, b = tee(iterable)
        next(b, None)
        return zip(a, b)

# ————————————————————— Division line ——————————————————————


n, = read()
a = read_list()
b = read_list()

dp = std.array2d(0, n, n)


for i in range(n):
    dp[0][i] = 1 if b[i] == a[0] else 0

for i in range(n):
    dp[i][0] = 1 if b[0] == a[i] else 0

for i in range(1, n):
    mx = 1
    for j in range(1, n):
        dp[i][j] = dp[i - 1][j]
        if a[i] == b[j]:
            dp[i][j] = std.max(dp[i][j], mx)
        if a[i] > b[j]:
            mx = std.max(mx, dp[i - 1][j] + 1)

res = 0
for i in range(n):
    res = std.max(dp[n - 1][i], res)

print(res)