i429. 4. 內積 (時限放寬版,給 Python 使用者)
Tags : APCS DP LCS 枚舉 貪心法
Accepted rate : 157人/184人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-13 16:12

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
12
Sample Input #2
5 5
-3 -3 -3 5 -5
-5 5 -3 -3 -3
Sample Output #2
77
Sample Input #3
4 3
1 2 3 4
-1 -2 -3
Sample Output #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
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$。

Tags:
APCS DP LCS 枚舉 貪心法
出處:
2022年6月APCS [管理者: algo.seacow@ ... (演算法海牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
32643 a0916933001@ ... (小律) i429
C++ 題解
448 2022-10-25 12:13
31151 u11031107 (立波器) i429
755 2022-07-15 10:05