2218 . 圓錐
TopCoder
Tags
Description
上體育課的時候，老師放了一排下圖這個東西，然後說：「我放了一些三角錐，等一下……」但你完全沒有心思去聽等一下要做什麼，因為你發現這些東西根本就不是三角錐，而是圓錐（如果忽視它上面那個洞的話）！
忿忿不平的你，決定要來破壞這一排「圓錐」。體育老師放了 $N$ 個圓錐排成一列，由左至右依序編號為 $1,2,\dots,N$。你發現，體育老師在第 $i$ 個圓錐上寫了一個數字 $A_i$，表示他對這個圓錐的珍惜程度（雖然你認為一個把圓錐說成三角錐的人不可能珍惜它）。
為了避免被老師發現你在搞破壞，你每次都只能偷走相鄰的 2 個或 3 個圓錐。在你一次偷走的圓錐中，如果有任兩個圓錐上面寫的數字是互質的，你就會覺得很不滿意，而你偷一次圓錐的滿意度是「你這次偷的圓錐中，兩兩相鄰的圓錐上面寫的數字的最大公因數總和」。換句話說，如果你一次偷了 $k$ 個圓錐，第 $i$ 個上面寫的數字是 $s_i$，那麼必須滿足：
- $k=2 \lor k=3$
- $\forall 1 \leq i \leq j \leq k,\ \gcd(s_i, s_j) > 1$
並且你獲得的滿足度是 $\sum_{i=1}^ {k-1} \gcd(s_i, s_{i+1})$。
在偷完一次圓錐後，體育老師會挪動一下剩下的圓錐，以避免圓錐之間有太大的間隔，但是圓錐的相對順序不會改變。
你希望把這排圓錐全部偷走，並且最大化每次偷圓錐的滿足度總和。
測資限制
- $2 \leq N \leq 500$
- $2 \leq A_i \leq 10^ 9$
Input Format
第一行有一個整數 $N$，表示體育老師放的圓錐數量。
第二行有 $N$ 個整數 $A_1,A_2,\dots,A_N$，表示體育老師在每個圓錐上寫的數字。
Output Format
輸出一個整數，表示你偷完圓錐後，每次偷圓錐的滿足度總和最大值。如果你不可能偷完所有圓錐，輸出 $-1$。
Sample Input 1
2 3 3 2 5 5 2
Sample Output 1
Sample Input 2
2 3 12 6 4
Sample Output 2
Sample Input 3
10 9 3 10 10
Sample Output 3
Sample Input 4
2 3 8 6 4
Sample Output 4
Hints
對於第一筆範測，你可以先偷走第 $2,3$ 個圓錐、再偷走第 $5,6$ 個圓錐，最後偷走第 $1,4,7$ 個圓錐。
Problem Source
2021 師大附中校隊培訓 模擬競賽
From NTU ADA 2021 Fall HW2
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~3 | 範例測資 | 0 |
| 2 | 4~17 | $N \le 10$ | 9 |
| 3 | 18~23 | $A_i$ 一定是質數，且若一種數字有出現，它會出現恰 $2$ 或 $3$ 次 | 11 |
| 4 | 4~17, 24~36 | $N \le 100$ | 31 |
| 5 | 0~47 | 無額外限制 | 49 |