輸入兩個長度分別為 $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。
子題配分
輸出一個整數代表內積最大值。
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
範例測資一可以將 $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$。
ID | User | Problem | Subject | Hit | Post Date |
41172 | glps1004@gma ... (Ian) | i402 | 142 | 2024-07-08 19:27 | |
38940 | qerpzzea@gma ... (賽希爾 cecill(陳宥穎)) | i402 | 389 | 2024-01-05 20:31 | |
37788 | edoctopus322 ... (Moon Jam) | i402 | 529 | 2023-10-08 12:07 | |
36810 | fire5386 (becaidorz) | i402 | 485 | 2023-08-09 23:10 | |
34341 | luray0601@gm ... (QWERTYPIG) | i402 | 640 | 2023-03-11 21:40 |