c054. 4. 內積

Content

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

Input

第一行輸入兩個正整數 $n$, $m$ $(1 \le n, m \le 1000)$，接下來一行有 $n$ 個整數 $A_1, \dots, A_n$，接下來一行有 $m$ 個整數 $B_1, \dots, B_m$，陣列的數值絕對值均不超過 100。

子題配分

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

Output

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

Sample Input #1

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

Sample Output #1

Sample Input #2

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

Sample Output #2

Sample Input #3

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

Sample Output #3

-1

測資資訊：

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

Hint ：

範例測資一可以將 $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$。

Python者送出解答時請用PYPY

Tags:

APCS DP LCS 枚舉貪心法

出處:

2022年6月 APCS 演算法海牛 [管理者： ktlai (K．我已霸榜．Tlai) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」