测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A6960. 信号的最佳共鸣

编程题 普及/提高-

题目描述

通信兵小李截获了两段加密的数字信号,分别记录为序列 $A$ 和序列 $B$。
序列 $A$ 包含 $N$ 个整数,序列 $B$ 包含 $M$ 个整数。

为了破解密码,小李需要找到这两段信号的“最大共鸣强度”。
具体的计算规则如下:
1. 从序列 $A$ 中挑选出一个子序列(保持原顺序)。
2. 从序列 $B$ 中挑选出一个**长度相同**的子序列(保持原顺序)。
3. 将这两个子序列对应位置的数字相乘,并将所有乘积相加,得到的结果就是“共鸣强度”。

**注意:**
- 选出的子序列**不能为空**(至少包含 1 个数字)。
- 你可以删除原序列中的某些数字,但不能改变剩余数字的相对顺序。

请你帮助小李计算出,能够获得的的**最大共鸣强度**是多少。

输入格式

第一行包含一个整数 $N$,表示序列 $A$ 的长度。
第二行包含 $N$ 个整数,表示序列 $A$ 的内容。
第三行包含一个整数 $M$,表示序列 $B$ 的长度。
第四行包含 $M$ 个整数,表示序列 $B$ 的内容。

输出格式

输出一个整数,表示最大的共鸣强度。

输入输出样例

输入 #1
4
2 1 -2 5
3
3 0 -6
输出 #1
18
输入 #2
2
3 -2
3
2 -6 7
输出 #2
21
输入 #3
2
-1 -1
2
1 1
输出 #3
-1

说明/提示

## 样例解释与数据范围

### 样例 #1 解释
- 序列 $A$: [2, 1, -2, 5]
- 序列 $B$: [3, 0, -6]
- 我们可以从 $A$ 中选出子序列 [2, -2] (下标 0, 2)。
- 从 $B$ 中选出子序列 [3, -6] (下标 0, 2)。
- 对应位置相乘求和:$2 \times 3 + (-2) \times (-6) = 6 + 12 = 18$。
- 这是能得到的最大值。

### 样例 #3 解释
- 序列 $A$: [-1, -1] (全负)
- 序列 $B$: [1, 1] (全正)
- 无论怎么选,乘积都是负数。为了让结果最大(最接近 0),我们只选一组:$(-1) \times 1 = -1$。
- 注意:题目要求子序列**非空**,所以不能选空集(结果为 0),必须选这一对,答案是 -1。

### 数据范围

- 对于 $100\%$ 的数据:
- $1 \le N, M \le 500$
- $-1000 \le \text{信号数值} \le 1000$

**数据点分布:**
- 测试点 1-5:$N, M \le 10$
- 测试点 6-15:$N, M \le 100$
- 测试点 16-25:$N, M \le 500$
上一题 去做题 下一题