APCS 先加後乘與函數 (zerojudge j607)
給一個運算式,運算式的內容由數字、+、* 和 \(f()\) 某個函式 \(f()\) 所組成,除了函式 \(f()\) 以外不會有額外的括號。請將此運算式依照先加後乘的方式運算。
函式 \(f()\) 定義為從這個不定長度的參數 \(x_1, x_2, x_3, x_4, ...\) 中的最大值扣掉最小值。例如 \(f(3,6,2)=6-2=4\),\(f(3)=0\)。
你有兩個數組分別為 \(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 \times B_j + A_{i+1} \times B_{j+1} +
A_{i+2} \times B_{j+2} + \dots + A_{i+r-1} \times
B_{j+r-1}\]
或可以簡單寫成 \(\sum_{k=0}^{r-1} A_{i+k}
\times B_{j+k}\)
已知有 \(n\) 個寶盒編號 \(0\) 到 \(n-1\) 以及 \(m\) 種鑰匙編號 \(0\) 到 \(m-1\)。一開始你有 \(t\) 種鑰匙分別為 \(x_1,..., x_t\)
每一個寶盒要打開都需要同時擁有 \(k\) 種鑰匙,第 \(i\) 個寶盒分別需要 \(r_{i1},r_{i2}, ... ,
r_{ik}\) 種類的鑰匙。每個寶盒打開後都會得到 \(k\) 種鑰匙,第個寶盒打開後分別會得到 \(s_{i1},s_{i2}, ... ,
s_{ik}\) 種類的鑰匙,當拿到新的鑰匙之後可以繼續開啟新的寶盒。保證寶盒內的鑰匙不會重複,並且每種鑰匙可以開啟的寶盒數量不超過 \(60\)。
請輸出最多可以開啟多少個寶盒。