13 友好数组

题目描述

给定数组 A 和 B，求它们的最长友好子数组长度。

友好数组定义：对于长度 l 的数组 a, b，若满足：

• $a_1 = b_1$
• $bi - a_i = b{i+1} - a_{i+1} - 1$（即 $b_i = a_i + i - 1$）

解题思路

公式推导

由定义可得：

• $b_1 - a_1 = 0 \Rightarrow b_1 = a_1$
• $b_2 - a_2 = 1 \Rightarrow b_2 = a_2 + 1$
• $b_3 - a_3 = 2 \Rightarrow b_3 = a_3 + 2$
• …

即友好数组需满足：$b_i = a_i + (i-1)$

DP 设计

$dp[i][j]$：考虑 A 前 i 个和 B 前 j 个的最长友好数组长度

转移方程：

• 若 $A[i-1] + dp[i-1][j-1] == B[j-1]$，则 $dp[i][j] = dp[i-1][j-1] + 1$
• 否则 $dp[i][j] = \max(dp[i-1][j], dp[i][j-1])$

这类似 LCS（最长公共子序列）的变形。

代码实现

n, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# dp[i][j]: 考虑A前i个和B前j个的最长友好数组长度
dp = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, m + 1):
        if A[i - 1] + dp[i - 1][j - 1] == B[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

print(dp[n][m])

复杂度分析

• 时间复杂度：$O(n \times m)$
• 空间复杂度：$O(n \times m)$

关键点

1. 友好数组等价于 $b_i = a_i + (i-1)$
2. 状态转移类似 LCS，但条件不同
3. $A[i-1] + dp[i-1][j-1] == B[j-1]$ 表示可以继续延伸友好关系