A6960. 信号的最佳共鸣
编程题
普及/提高-
知识点
题目描述
通信兵小李截获了两段加密的数字信号,分别记录为序列 $A$ 和序列 $B$。
序列 $A$ 包含 $N$ 个整数,序列 $B$ 包含 $M$ 个整数。
为了破解密码,小李需要找到这两段信号的“最大共鸣强度”。
具体的计算规则如下:
1. 从序列 $A$ 中挑选出一个子序列(保持原顺序)。
2. 从序列 $B$ 中挑选出一个**长度相同**的子序列(保持原顺序)。
3. 将这两个子序列对应位置的数字相乘,并将所有乘积相加,得到的结果就是“共鸣强度”。
**注意:**
- 选出的子序列**不能为空**(至少包含 1 个数字)。
- 你可以删除原序列中的某些数字,但不能改变剩余数字的相对顺序。
请你帮助小李计算出,能够获得的的**最大共鸣强度**是多少。
序列 $A$ 包含 $N$ 个整数,序列 $B$ 包含 $M$ 个整数。
为了破解密码,小李需要找到这两段信号的“最大共鸣强度”。
具体的计算规则如下:
1. 从序列 $A$ 中挑选出一个子序列(保持原顺序)。
2. 从序列 $B$ 中挑选出一个**长度相同**的子序列(保持原顺序)。
3. 将这两个子序列对应位置的数字相乘,并将所有乘积相加,得到的结果就是“共鸣强度”。
**注意:**
- 选出的子序列**不能为空**(至少包含 1 个数字)。
- 你可以删除原序列中的某些数字,但不能改变剩余数字的相对顺序。
请你帮助小李计算出,能够获得的的**最大共鸣强度**是多少。
输入格式
第一行包含一个整数 $N$,表示序列 $A$ 的长度。
第二行包含 $N$ 个整数,表示序列 $A$ 的内容。
第三行包含一个整数 $M$,表示序列 $B$ 的长度。
第四行包含 $M$ 个整数,表示序列 $B$ 的内容。
第二行包含 $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$:
- 序列 $B$:
- 我们可以从 $A$ 中选出子序列
- 从 $B$ 中选出子序列
- 对应位置相乘求和:$2 \times 3 + (-2) \times (-6) = 6 + 12 = 18$。
- 这是能得到的最大值。
### 样例 #3 解释
- 序列 $A$:
- 序列 $B$:
- 无论怎么选,乘积都是负数。为了让结果最大(最接近 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$
### 样例 #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$