i429. 4. 內積 (時限放寬版，給 Python 使用者)

內容

輸入兩個長度分別為 $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}$ 。

輸入說明

第一行輸入兩個正整數 $n$ , $m$ $(1 \leq n, m \leq 1000)$ ，接下來一行有 $n$ 個整數 $A_{1}, \dots, A_{n}$ ，接下來一行有 $m$ 個整數 $B_{1}, \dots, B_{m}$ ，陣列的數值絕對值均不超過 100。

子題配分

(20%): $1 \leq n, m \leq 200$
(80%): 無額外限制

輸出說明

輸出一個整數代表內積最大值。

範例輸入 #1

5 5
-3 -3 3 3 -3
2 2 2 2 2

範例輸出 #1

範例輸入 #2

5 5
-3 -3 -3 5 -5
-5 5 -3 -3 -3

範例輸出 #2

範例輸入 #3

4 3
1 2 3 4
-1 -2 -3

範例輸出 #3

-1

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 2.0s , <1K
公開測資點#1 (5%): 2.0s , <1K
公開測資點#2 (5%): 2.0s , <1K
公開測資點#3 (5%): 2.0s , <1K
公開測資點#4 (5%): 2.0s , <1M
公開測資點#5 (5%): 2.0s , <1M
公開測資點#6 (5%): 2.0s , <1M
公開測資點#7 (5%): 2.0s , <1M
公開測資點#8 (5%): 2.0s , <1M
公開測資點#9 (5%): 2.0s , <1M
公開測資點#10 (5%): 2.0s , <1M
公開測資點#11 (5%): 2.0s , <1M
公開測資點#12 (5%): 2.0s , <1M
公開測資點#13 (5%): 2.0s , <1M
公開測資點#14 (5%): 2.0s , <1M
公開測資點#15 (5%): 2.0s , <1M
公開測資點#16 (5%): 2.0s , <1M
公開測資點#17 (5%): 2.0s , <1M
公開測資點#18 (5%): 2.0s , <1M
公開測資點#19 (5%): 2.0s , <1M

提示：

範例測資一可以將 $a$ 取 $A_{3}$ , $A_{4}$ ， $b$ 取 $B_{1}$ , $B_{2}$ ，內積起來為 $12$ 。

範例測資二可以將 $a$ 取 $A_{1}$ , $A_{2}$ , $A_{3}$ , $A_{4}$ , $A_{5}$ ， $b$ 取 $B_{5}$ , $B_{4}$ , $B_{3}$ , $B_{2}$ , $B_{1}$ ，總和為 $77$ 。

範例測資三可以將 $a$ 取 $A_{1}$ ， $b$ 取 $B_{1}$ ，總和為 $- 1$ 。

標籤:

APCS DP LCS 枚舉貪心法

出處:

2022年6月 APCS [管理者： algo.seacow@gmail.com

algo.seacow@ ... (演算法海牛) ]

編號	身分	題目	主題	人氣	發表日期
32643	a0916933001@ ... (小律)	i429	C++ 題解	521	2022-10-25 12:13
31151	u11031107 (立波器)	i429	沒有頭緒的可以先寫這題	821	2022-07-15 10:05