a308:
4. 內積[202206APCS]
內容
輸入說明
第一行輸入兩個正整數 n, m (1≤n,m≤1000)，接下來一行有 n 個整數 A1,…,An，接下來一行有 m 個整數 B1,…,Bm，陣列的數值絕對值均不超過 100。
子題配分
- (20%): 1≤n,m≤200
- (80%): 無額外限制
輸出說明
輸出一個整數代表內積最大值。
範例輸入
#1
5 5 -3 -3 3 3 -3 2 2 2 2 2
範例輸出
#1
12
範例輸入
#2
5 5 -3 -3 -3 5 -5 -5 5 -3 -3 -3
範例輸出
#2
77
範例輸入
#3
4 3 1 2 3 4 -1 -2 -3
範例輸出
#3
-1
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1K
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1K
提示 ：
提示 ：
範例測資一可以將 a 取 A3, A4，b 取 B1, B2，內積起來為 12。
範例測資二可以將 a 取 A1, A2, A3, A4, A5，b 取 B5, B4, B3, B2, B1，總和為 77。
範例測資三可以將 a 取 A1，b 取 B1，總和為 −1。
- 先建立一個sq[][] 存 x[i] * y[j] 的值
- prefix_sum 所有斜直線的值取max即為答案（記得注意陣列要倒轉）
出處:
2022年06月APCS演算法海牛
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||