# APCS實作題2022年6月第4題：內積 > 日期：2024年8月3日 > 作者：王一哲 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=i402) > [ZeroJudge 題目連結時限放寬版](https://zerojudge.tw/ShowProblem?problemid=i429) ## 題目 ### 問題描述 輸入兩個長度分別為 $n$ 和 $m$ 的陣列 $A_1, A_2, \dots, A_n$ 以及 $B_1, B_2, \dots, B_m$。你可以自由決定是否要將 $A, B$ 做翻轉(reverse)，也可以自由決定一個正整數 $r$。目標要在 $A, B$ 分別找一個長度 $r$ 的子區間(subarray)，並讓這兩個子區間的內積最大化。 內積的定義如下： 假設在 $A$ 陣列選出了一段長度 $r$ 的子區間 $A_i, A_{i+1}, A_{i+2}, \dots, A_{i+r-1}$，並在 $B$ 陣列選出了一段長度 $r$ 的子區間 $B_j, B_{j+1}, B_{j+2}, \dots, B_{j+r-1}$，這兩個子區間的內積就是 $A_i B_j + A_{i+1} B_{j+1} + A_{i+2} B_{j+2} + \dots + A_{i+r-1} B_{j+r-1}$，也可以寫成 $\sum_{k=0}^{r-1} A_{i+k} B_{j+k}$。 <br /> ### 輸入說明 第一行輸入兩個正整數 $n, m ~(1 \leq n, m \leq 1000)$，接下來一行有 $n$ 個整數 $A_1, A_2, \dots, A_n$，接下來一行有 $m$ 個整數 $B_1, B_2, B_m$，陣列的數值絕對值均不超過 100。 子題配分 - 20%：$1 \leq n, m \leq 200$ - 80%：無額外限制 <br /> ### 輸出格式 輸出一個整數代表內積最大值。 <br /> ### 範例輸入1 ``` 5 5 -3 -3 3 3 -3 2 2 2 2 2 ``` ### 範例輸出1 ``` 12 ``` ### 範例輸入2 ``` 5 5 -3 -3 -3 5 -5 -5 5 -3 -3 -3 ``` ### 範例輸出2 ``` 77 ``` ### 範例輸入3 ``` 4 3 1 2 3 4 -1 -2 -3 ``` ### 範例輸出3 ``` -1 ``` <br /><br /> ## Python 程式碼 ### 寫法1，用二維串列記錄內積的最大值，會超時 如果串列A的長度為n、串列B的長度為m，建立一個 (n+1)\*(m+1) 的二維串列 dp，所有資料皆預設為0，dp[i][j] 為串列 A[0] ~ A[i-1]、 B[0] ~ B[i-1] 內積的最大值，對應到程式碼的第7行 ```python dp[i][j] = max(dp[i-1][j-1] + a[i-1]*b[j-1], a[i-1]*b[j-1]) ``` 如果 dp[i-1][j-1] < 0，則取 a[i-1]\*b[j-1]。 這個寫法在第4筆測資開始超時。 ```python= def solve(a, b): # 自訂函式，輸入串列a,b，找內積最大值 imax = -100000 # 目前的最大值，由於題目限制串列資料絕對值小於100，相乘後小於10000，不可能小於預設值 na, mb = len(a), len(b) # 串列a、b的長度 dp = [[0]*(mb+1) for _ in range(na+1)] # 儲存內積最大值用的二維串列 for i in range(1, na+1): for j in range(1, mb+1): dp[i][j] = max(dp[i-1][j-1] + a[i-1]*b[j-1], a[i-1]*b[j-1]) imax = max(imax, dp[i][j]) # 更新最大值 return imax # 回傳最大值 n, m = map(int, input().split()) # 讀取 n、m A = list(map(int, input().split())) # 讀取 A B = list(map(int, input().split())) # 讀取 B ans = -100000 # 答案，預設為 -100000 ans = max(ans, solve(A, B)) # 呼叫 solve，代入 A、B 求答案 A = A[::-1] # 反轉串列 A ans = max(ans, solve(A, B)) # 呼叫 solve，代入反轉後的 A、原來的 B 求答案 B = B[::-1] # 反轉串列 B ans = max(ans, solve(A, B)) # 呼叫 solve，代入反轉後的 A、反轉後的 B 求答案 A = A[::-1] # 反轉串列 A，轉回原來的順序 ans = max(ans, solve(A, B)) # 呼叫 solve，代入原來的 A、反轉後的 B 求答案 print(ans) # 印出答案 ``` <br /><br /> ### 寫法2，逐步更新內積最大值 時限放寬版，費時最久約為 1.7 s，使用記憶體最多約為 3.5 MB，通過測試。普通版第4筆測資超時。 ```python= def solve(a, b): # 自訂函式，輸入串列a,b，找內積最大值 imax = -100000 # 目前的最大值，預設為 -100000 na, mb = len(a), len(b) # 串列a、b的長度 for i in range(na): # 依序檢查 a[0] ~ a[na-1] tot, p, q = 0, i, 0 # 目前的內積加總 tot，由 a 讀資料的索引值 p，由 b 讀資料的索引值 q while p < na and q < mb: # 如果 p、q 都還沒有出界時繼續執行 if tot < 0: tot = 0 # 如果 tot 小於 0，重設為 0 tot += a[p]*b[q] # 更新 tot，加上 a[p]*b[q] imax = max(imax, tot) # 更新 imax p += 1; q += 1 # 更新p、q return imax # 回傳 imax n, m = map(int, input().split()) # 讀取 n、m A = list(map(int, input().split())) # 讀取 A B = list(map(int, input().split())) # 讀取 B ans = -100000 # 答案，預設為 -100000 ans = max(ans, solve(A, B)) # 呼叫 solve，代入 A、B 求答案 A = A[::-1] # 反轉串列 A ans = max(ans, solve(A, B)) # 呼叫 solve，代入反轉後的 A、原來的 B 求答案 B = B[::-1] # 反轉串列 B ans = max(ans, solve(A, B)) # 呼叫 solve，代入反轉後的 A、反轉後的 B 求答案 A = A[::-1] # 反轉串列 A，轉回原來的順序 ans = max(ans, solve(A, B)) # 呼叫 solve，代入原來的 A、反轉後的 B 求答案 print(ans) # 印出答案 ``` <br /><br /> 以上的程式碼中，第6 ~ 10行也可以改用 for 迴圈。時限放寬版，費時最久約為 1.3 s，使用記憶體最多約為 3.5 MB，通過測試。 ```python= tot = 0 # 目前的內積加總 tot for p, q in zip(range(i, na), range(mb)): # 如果 p、q 都還沒有出界時繼續執行 if tot < 0: tot = 0 # 如果 tot 小於 0，重設為 0 tot += a[p]*b[q] # 更新 tot，加上 a[p]*b[q] imax = max(imax, tot) # 更新 imax ``` <br /><br /> ## C++ 程式碼 ### 寫法1，用二維串列記錄內積的最大值 普通版及時限放寬版，費時最久約為 14 ms，使用記憶體最多約為 15.5 MB，通過測試。 ```cpp= #include <iostream> #include <vector> #include <algorithm> using namespace std; int solve(vector<int> a, vector<int> b) { // 自訂函式，輸入陣列a, b，找內積最大值 int imax = -100000; // 目前的最大值，由於題目限制串列資料絕對值小於100，相乘後小於10000，不可能小於預設值 int n = (int)a.size(), m = (int)b.size(); // 陣列a、b的長度 vector<vector<int>> dp (n+1, vector<int> (m+1, 0)); // 儲存內積最大值用的二維串列 for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { dp[i][j] = max(dp[i-1][j-1] + a[i-1]*b[j-1], a[i-1]*b[j-1]); imax = max(imax, dp[i][j]); // 更新最大值 } } return imax; // 回傳最大值 } int main() { ios::sync_with_stdio(0); cin.tie(0); // 加速 int n, m; cin >> n >> m; // 讀取 n、m vector<int> A (n, 0), B (m, 0); // 陣列A、B for(int i=0; i<n; i++) cin >> A[i]; // 讀取 A for(int i=0; i<m; i++) cin >> B[i]; // 讀取 B int ans = -100000; // 答案，預設為 -100000 ans = max(ans, solve(A, B)); // 呼叫 solve，代入 A、B 求答案 reverse(A.begin(), A.end()); // 反轉 A ans = max(ans, solve(A, B)); // 呼叫 solve，代入反轉後的 A、原來的 B 求答案 reverse(B.begin(), B.end()); // 反轉 B ans = max(ans, solve(A, B)); // 呼叫 solve，代入反轉後的 A、反轉後的 B 求答案 reverse(A.begin(), A.end()); // 反轉 A，轉回原來的順序 ans = max(ans, solve(A, B)); // 呼叫 solve，代入原來的 A、反轉後的 B 求答案 cout << ans << "\n"; // 印出答案 return 0; } ``` <br /><br /> ### 寫法2，逐步更新內積最大值 普通版及時限放寬版，費時最久約為 5 ms，使用記憶體最多約為 380 kB，通過測試。 ```cpp= #include <iostream> #include <vector> #include <algorithm> using namespace std; int solve(vector<int> a, vector<int> b) { // 自訂函式，輸入陣列a, b，找內積最大值 int imax = -100000; // 目前的最大值，由於題目限制串列資料絕對值小於100，相乘後小於10000，不可能小於預設值 int n = (int)a.size(), m = (int)b.size(); // 陣列a、b的長度 for(int i=0; i<n; i++) { // 依序檢查 a[0] ~ a[n-1] int tot = 0; // 目前的內積加總 for(int p=i, q=0; p<n && q<m; p++, q++) { // 如果 p、q 都還沒有出界時繼續執行 if (tot < 0) tot = 0; // 如果 tot 小於 0，重設為 0 tot += a[p]*b[q]; // 更新 tot，加上 a[p]*b[q] imax = max(imax, tot); // 更新最大值 } } return imax; // 回傳最大值 } int main() { ios::sync_with_stdio(0); cin.tie(0); // 加速 int n, m; cin >> n >> m; // 讀取 n、m vector<int> A (n, 0), B (m, 0); // 陣列A、B for(int i=0; i<n; i++) cin >> A[i]; // 讀取 A for(int i=0; i<m; i++) cin >> B[i]; // 讀取 B int ans = -100000; // 答案，預設為 -100000 ans = max(ans, solve(A, B)); // 呼叫 solve，代入 A、B 求答案 reverse(A.begin(), A.end()); // 反轉 A ans = max(ans, solve(A, B)); // 呼叫 solve，代入反轉後的 A、原來的 B 求答案 reverse(B.begin(), B.end()); // 反轉 B ans = max(ans, solve(A, B)); // 呼叫 solve，代入反轉後的 A、反轉後的 B 求答案 reverse(A.begin(), A.end()); // 反轉 A，轉回原來的順序 ans = max(ans, solve(A, B)); // 呼叫 solve，代入原來的 A、反轉後的 B 求答案 cout << ans << "\n"; // 印出答案 return 0; } ``` <br /><br /> --- ###### tags:`APCS`、`Python`、`C++`