T2-2 信号的最佳共鸣

核心思想

这是一道最长公共子序列（LCS）的变形题，不是求长度，而是求对应位置乘积和的最大值。

状态定义

dp[i][j] = 考虑序列A的前i个数、序列B的前j个数时，
           至少选择1对数字配对的最大共鸣强度

• i 遍历序列A（0到N）
• j 遍历序列B（0到M）
• 初始值：全部设为 -INF（表示还没有合法方案）

状态转移（核心）

对于每个位置 (i, j)，有三种决策：

1️⃣ 不选A[i]（跳过A的当前数）

dp[i][j] = max(dp[i][j], dp[i-1][j]);

从 (i-1, j) 转移过来，相当于A往前退一步

2️⃣ 不选B[j]（跳过B的当前数）

dp[i][j] = max(dp[i][j], dp[i][j-1]);

从 (i, j-1) 转移过来，相当于B往前退一步

3️⃣ 选择A[i]和B[j]配对（关键）

这一步有两种可能：

a) 这是第一对数

dp[i][j] = max(dp[i][j], A[i] * B[j]);

直接用这一对的乘积作为结果（满足"至少选1对"）

b) 累加到之前的结果

if (dp[i-1][j-1] > -INF) {
    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + A[i] * B[j]);
}

如果 (i-1, j-1) 已经有合法方案，就累加当前这对的乘积

为什么这样写？

关键点1：自动处理"至少1对"

• 不用单独记录选了几对（省去第三维）
• 初始化为 -INF，只有真正配对后才有有效值
• 每次配对都考虑"作为第一对"或"累加到已有结果"

关键点2：保持子序列顺序

• dp[i-1][j-1] 确保了配对的两个数都是按原序列顺序选的
• 类似LCS，对角线转移保证顺序性

图解样例1

A = [2, 1, -2, 5]
B = [3, 0, -6]

最优方案：选 A[1]=2 和 B[1]=3 配对 → 2×3 = 6
         选 A[3]=-2 和 B[3]=-6 配对 → (-2)×(-6) = 12
         总和 = 18

DP表推导（部分关键值）：

dp[1][1] = 2×3 = 6
dp[3][3] = max(dp[2][2] + (-2)×(-6)) 
         = max(6 + 12) = 18 ✅

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, M;
    cin >> N;
    vector<long long> A(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];
    
    cin >> M;
    vector<long long> B(M + 1);
    for (int j = 1; j <= M; j++) cin >> B[j];
    
    const long long INF = -1e18;
    // dp[i][j]: 考虑A前i个、B前j个，至少选1对的最大值
    vector<vector<long long>> dp(N + 1, vector<long long>(M + 1, INF));
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            // 不选A[i]
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
            
            // 不选B[j]
            dp[i][j] = max(dp[i][j], dp[i][j-1]);
            
            // 选A[i]和B[j]配对
            long long val = A[i] * B[j];
            // 这是第一对（从空集转移）
            dp[i][j] = max(dp[i][j], val);
            // 或者累加到之前的结果
            if (dp[i-1][j-1] > INF) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-1] + val);
            }
        }
    }
    
    cout << dp[N][M] << endl;
    return 0;
}