传送门
注：如无特殊说明，本篇题解中所有的序列，均用红色标示已经放置硬币的位置。若本次操作为拿走硬币，用蓝色标示本次操作拿走的硬币的位置，用黑色标示从未放过硬币或放置过硬币且在本次操作之前的操作中被拿走的位置。
根据题意和数据范围，不难想到本题的做法是区间 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;
}