題目描述

吃貨"和"饞嘴"兩人到披薩店點了一份鐵盤（圓形）披薩，并囑咐店員將披薩按放射狀切成大小相同的偶數個小塊。但是粗心的服務員將披薩切成了每塊大小都完全不同奇數塊，且肉眼能分辨出大小。
由于兩人都想吃到最多的披薩，他們商量了一個他們認為公平的分法：從"吃貨"開始，輪流取披薩。除了第一塊披薩可以任意選取外，其他都必須從缺口開始選。
他倆選披薩的思路不同。"饞嘴"每次都會選最大塊的披薩，而且"吃貨"知道"饞嘴"的想法。
已知披薩小塊的數量以及每塊的大小，求"吃貨"能分得的最大的披薩大小的總和。

輸入描述

第 1 行為一個正整數奇數 N，表示披薩小塊數量。

• 3 ≤ N < 500

接下來的第 2 行到第 N + 1 行（共 N 行），每行為一個正整數，表示第 i 塊披薩的大小

• 1 ≤ i ≤ N

披薩小塊從某一塊開始，按照一個方向次序順序編號為 1 ~ N

• 每塊披薩的大小范圍為 [1, 2147483647]

輸出描述

吃貨"能分得到的最大的披薩大小的總和。

用例1

輸入:
5
8
2
10
5
7

輸出:
19

說明:
此例子中，有 5 塊披薩。每塊大小依次為 8、2、10、5、7。
按照如下順序拿披薩，可以使"吃貨"拿到最多披薩：
“吃貨” 拿大小為 10 的披薩
“饞嘴” 拿大小為 5 的披薩
“吃貨” 拿大小為 7 的披薩
“饞嘴” 拿大小為 8 的披薩
“吃貨” 拿大小為 2 的披薩
至此，披薩瓜分完畢，"吃貨"拿到的披薩總大小為 10 + 7 + 2 = 19
可能存在多種拿法，以上只是其中一種。

解題思路

給定一個環形排列的披薩數組，每塊披薩有一個美味值，需要計算出從任意位置開始，能夠獲得的最大美味值總和。

1. 環形處理：由于披薩是環形排列的，所以在選擇披薩時需要考慮邊界情況，即當選擇了最左邊或最右邊的披薩后，如何循環到另一端。

2. 動態規劃：使用一個二維數組 dp 作為記憶化存儲，其中 dp[L][R] 表示從左邊界 L 到右邊界 R 能夠獲得的最大美味值。如果 dp[L][R] 已經被計算過，則直接返回該值。

3. 遞歸計算：定義一個遞歸函數來計算 dp[L][R]。如果 a[L]（左邊界的披薩美味值）大于 a[R]（右邊界的披薩美味值），則選擇 L 并將L向右移動一位；否則選擇 R 并將 R 向左移動一位。這樣遞歸地選擇下一步，直到只剩下一塊披薩。

4. 遞歸基：當左右邊界相遇時（即 L == R），說明只剩下一塊披薩，直接返回這塊披薩的美味值作為遞歸基。

5. 狀態轉移：在遞歸過程中，dp[L][R] 的值是通過比較選擇左邊界披薩和右邊界披薩后，剩下披薩的最大美味值之和來確定的。

Python3源碼

# 讀取披薩的數量
n = int(input())
# 讀取每塊披薩的美味值
arr = [int(input()) for _ in range(n)]# 初始化 dp 數組，dp為記憶化數組，用于存儲已計算過的狀態
dp = [[-1]*n for _ in range(n)]#計算最大披薩的函數
def cal_max(L,R):# 如果已計算過，直接返回結果if dp[L][R] != -1:return dp[L][R]# 根據美味值選擇吃掉左邊或右邊的披薩if arr[L] > arr[R]:L = (L+1)%nelse:R = (R+n-1)%n# 如果只剩一塊披薩，返回其美味值if L == R:dp[L][R] = arr[L]else:dp[L][R] = max(arr[L]+cal_max((L+1)%n,R),arr[R]+cal_max(L,(R+n-1)%n))return dp[L][R]# 初始化最大美味值為 0
ans = 0
# 計算并更新最大美味值
for i in range(n):ans = max(ans,cal_max((i+1)%n,(i+n-1)%n)+arr[i])# 輸出最多能吃到的披薩的美味值總和
print(ans)