輸入兩個長度分別為 $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 \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%): 無額外限制
輸出一個整數代表內積最大值。
5 5 -3 -3 3 3 -3 2 2 2 2 2
12
5 5 -3 -3 -3 5 -5 -5 5 -3 -3 -3
77
4 3 1 2 3 4 -1 -2 -3
-1
公開 測資點#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$。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 32643 |
|
i429 | 435 | 2022-10-25 12:13 | |
| 31151 | u11031107 (立波器) | i429 | 736 | 2022-07-15 10:05 |