內積 題解｜APCS 2022 年 6 月高級 第 4 題

前置知識

這題是「最大連續和」搬到乘積表的斜線上，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 最大連續子陣列（Kadane）：吳邦一《AP325》第 4 章的 P-4-13（教材 PDF 第 133～134 頁；站上 ap325p413）——「以 \(i\) 結尾的最大和＝\(A_i\) 加上『前面那段有賺才接』」就是本題的轉移；NTUCPC Guide〈狀態與轉移〉補齊 DP 的講法。
• 二維的 DP 表：NTUCPC Guide〈多個維度的 DP〉——本題的狀態是一對下標 \((i, j)\)。
• 語法書：2.9 估一下答案會不會超過 int；二維表用巢狀 vector 開。

簡潔題意

兩個整數序列 \(A\)（長 \(n\)）、\(B\)（長 \(m\)），可以把其中一個（或兩個）反轉，再各選一段等長、非空的連續片段，對應位置相乘再相加。求最大值（\(1 \le n, m \le 1000\)，\(-100 \le A_i, B_j \le 100\)；答案可能是負的）。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(20\) 分）：\(n, m \le 200\)。
• 子題組 2（\(80\) 分）：無額外限制。

先把「反轉」想清楚：只有兩張乘積表

把 \(A_i \times B_j\) 排成 \(n \times m\) 的表，一對等長片段「\(A\) 從 \(i\) 開始、\(B\) 從 \(j\) 開始、長 \(L\)」就是表上從 \((i, j)\) 往右下走 \(L\) 格的一條斜線，內積是斜線上的格子總和。反轉會怎樣：只反轉 \(B\) 和只反轉 \(A\) 得到的配對一模一樣（同樣的兩段，差別只是誰正誰反）；兩個都反轉等於都不反轉（兩段一起倒過來、乘積照舊相加）。所以只要算兩張表——\(B\) 原樣一張、\(B\) 反轉一張——取大的。

先拿下 20 分：枚舉起點，一格一格延長

對每個起點 \((i, j)\)，沿斜線往右下走、邊走邊累加，每走一步都拿目前的和去更新答案；延長一格只多一次乘加，不必每種長度重算。答案初值要用 INT_MIN：不能選空的片段，全是負數時答案就是負的。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;
    int best = INT_MIN;                              // 一定要選非空的段，所以不能從 0 起跳
    for (int pass = 0; pass < 2; pass++) {           // 第二輪把 B 反轉再做一次
        for (int i = 0; i < n; i++) {                // A 那一段的起點
            for (int j = 0; j < m; j++) {            // B 那一段的起點
                int sum = 0;
                for (int t = 0; i + t < n && j + t < m; t++) {   // 兩段一起往右延長一格
                    sum += a[i + t] * b[j + t];
                    best = max(best, sum);
                }
            }
        }
        reverse(b.begin(), b.end());
    }
    cout << best << '\n';
    return 0;
}

所有斜線的總長約 \(\frac{nm \cdot \min(n, m)}{3}\)，兩張表在 \(n = m = 1000\) 時約 \(6.7 \times 10^8\) 次乘加，本站實測 \(0.45\) 秒——擠進 \(2\) 秒時限，但那是編譯器最佳化撐出來的；子題組 1 的 \(n, m \le 200\)（約 \(5 \times 10^6\) 次）才是它真正穩的範圍。

從 20 分到 100 分：每條斜線做一次最大連續和

同一條斜線上的格子排成一個數列，「選一段非空連續、和最大」正是最大連續子陣列。令 endHere[i][j] 是兩段分別以 \(A_i\)、\(B_j\) 結尾（等長、非空）的最大內積：最後一對一定貢獻 \(A_i B_j\)，前面要嘛接上以 \((i-1, j-1)\) 結尾的最佳段、要嘛從這一對重新開始——

全部格子取最大就是這張表的答案。圖 1 是範例 2 反轉 \(B\) 之後的表，主對角線 \(9 + 9 + 9 + 25 + 25 = 77\)。每格 \(O(1)\)，兩張表 \(O(nm)\)，\(n = m = 1000\) 本站實測 \(0.01\) 秒。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;
    int best = INT_MIN;                              // 不能選空的段，所以不能從 0 起跳
    for (int pass = 0; pass < 2; pass++) {           // 第二輪把 B 反轉再做一次
        // endHere[i][j]：兩段分別以 a[i-1]、b[j-1] 結尾（等長、非空）的最大內積
        vector<vector<int>> endHere(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int product = a[i - 1] * b[j - 1];
                endHere[i][j] = product + max(0, endHere[i - 1][j - 1]);   // 前面那一段有賺才接上
                best = max(best, endHere[i][j]);
            }
        }
        reverse(b.begin(), b.end());
    }
    cout << best << '\n';
    return 0;
}

數值範圍：一格最大 \(100 \times 100 = 10^4\)，一條斜線最長 \(1000\) 格，答案的絕對值不超過 \(10^7\)，int 綽綽有餘。表格多開一列一行當第 \(0\) 列、第 \(0\) 行（值 \(0\)），endHere[i-1][j-1] 在邊界上就不用特判。

測過再交：範例只蓋到「全負」與「要反轉」

三個範例蓋到了全負（範例 3 的 \(-1\)）和要反轉（範例 2）。沒蓋到：\(n = m = 1\)、答案剛好是 \(0\)、負負得正的極端值、中間夾一個負數要不要繼續、\(m = 1\)、最大規模。

八筆都親眼看過正確，這題就穩了。