傳送門

注：如無特殊說明，本篇題解中所有的序列，均用紅色標示已經放置硬幣的位置。若本次操作為拿走硬幣，用藍色標示本次操作拿走的硬幣的位置，用黑色標示從未放過硬幣或放置過硬幣且在本次操作之前的操作中被拿走的位置。

根據題意和數據范圍，不難想到本題的做法是區間 DP。然而難點在于刻畫放置和拿走硬幣這兩個操作。

舉個例子，考慮序列 \([\textcolor{red}5,\textcolor{red}4,\textcolor{red}{-2},-3,-1,6]\)，其中前三個位置放置了硬幣。此時的分數和是 \(7\)，還能不能更大呢？

考慮先將后三個位置也放上硬幣，然后再將第 \(3\sim5\) 個位置的硬幣拿走，序列狀態變化為：\([\textcolor{red}{5},\textcolor{red}{4},\textcolor{red}{-2},\textcolor{red}{-3},\textcolor{red}{-1},\textcolor{red}{6}]\to [\textcolor{red}{5},\textcolor{red}{4},\textcolor{blue}{-2},\textcolor{blue}{-3},\textcolor{blue}{-1},\textcolor{red}{6}]\to[\textcolor{red}5,\textcolor{red}4,-2,-3,-1,\textcolor{red}6]\)，兩步操作后的分數和分別是 \(9\) 和 \(15\)。

我們發現如上操作的實質是把第 \(3\) 個位置的硬幣移動到第 \(6\) 個位置。類似地可以推斷出，第 \(i\) 個位置的硬幣只能由第 \(i±3k\) 個位置的硬幣移動而來。

如果只進行這一步轉化，還不足以分析出區間合并的方法。因此，我們再考慮一個序列 \([9,-5,-3,\textcolor{red}{-2},\textcolor{red}7,\textcolor{red}{-1},-6,-4,8]\)，其中第 \(4\sim 6\) 個位置放置了硬幣。此時的分數之和是 \(4\)，還能不能更大呢？

考慮如下的序列狀態變化：\( [9,-5,-3,\textcolor{red}{-2},\textcolor{red}7,\textcolor{red}{-1},-6,-4,8]\to[\textcolor{red}9,\textcolor{red}{-5},\textcolor{red}{-3},\textcolor{red}{-2},\textcolor{red}7,\textcolor{red}{-1},-6,-4,8]\to[\textcolor{red}9,\textcolor{blue}{-5},\textcolor{blue}{-3},\textcolor{blue}{-2},\textcolor{red}7,\textcolor{red}{-1},-6,-4,8]\to[\textcolor{red}9,-5,-3,-2,\textcolor{red}7,\textcolor{red}{-1},\textcolor{red}{-6},\textcolor{red}{-4},\textcolor{red}8]\to[\textcolor{red}9,-5,-3,-2,\textcolor{red}7,\textcolor{blue}{-1},\textcolor{blue}{-6},\textcolor{blue}{-4},\textcolor{red}8]\to[\textcolor{red}9,-5,-3,-2,\textcolor{red}7,-1,-6,-4,\textcolor{red}8] \)。每一步操作后的分數和分別是 \(5,15,13,24\)。

觀察到我們可以通過放置和拿走硬幣操作的組合，把連續放置的 \(3\) 個硬幣拆開，使左邊的位置為 \(i\) 的硬幣移動到 \(i-3\)，中間的位置為 \(j\) 的硬幣不動，右邊的位置為 \(k\) 的硬幣移動到 \(k+3\)。這樣我們就推導出了區間合并的方法。

設 \(f_{l,r}\) 表示區間 \([l,r]\) 能得到的最大分數和。對于一個長度為 \(3\) 的倍數的區間 \([l,r]\)，枚舉斷點 \(i\)，如果區間 \([l+1,i-1]\) 和 \([i+1,r-1]\) 的長度都是 \(3\) 的倍數，也即位置為 \(l\) 和 \(r\) 的硬幣都能夠分別移動到 \(i-1\) 和 \(i+1\) 的位置，那么就有 \(f_{l,r}=\max(f_{l,r},f_{l+1,i-1}+f_{i+1,r-1}+a_l+a_i+a_r)\)。對于所有區間，都套路地進行 \(f_{l,r}=\max(f_{l,r},f_{l,i}+f_{i+1,r})\) 的轉移。

最終的答案就是 \(f_{1,n}\)，時間復雜度 \(O(n^3)\)。

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n, a[N], f[N][N];
int main () {
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	for (int len = 1; len <= n; ++len)
		for (int l = 1, r = l + len - 1; r <= n; ++l, ++r) {
			if (len % 3 == 0)
				for (int i = l + 1; i < r; ++i) {
					if ((i - l + 1) % 3 != 2 || (r - i + 1) % 3 != 2)
						continue;
					f[l][r] = max(f[l][r], f[l + 1][i - 1] + f[i + 1][r - 1] + a[l] + a[i] + a[r]);
				}
			for (int i = l; i < r; ++i)
				f[l][r] = max(f[l][r], f[l][i] + f[i + 1][r]);
		}
	cout << f[1][n];
	return 0;
}