自动搬运

查看原文

来自洛谷，原作者为

	kai586123 啊嗯

搬运于2025-08-24 22:03:48，当前版本为作者最后更新于2019-01-23 22:24:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

同时发布于个人Blog：Baka's Blog

看到题目中的合并，可以发现本题是一道区间DP。

将合并分为合并两个饭团和合并三个饭团分开讨论。合并两个饭团的操作如同石子合并这道题，复杂度$O(N^3)$，不再讨论。显然，合并两个饭团不是解决本题的瓶颈。

考虑合并三个饭团的暴力做法。在区间内枚举中间区间的左右端点，判断可否合并，复杂度$O(N^4)$，无法通过本题。

观察本题的特殊性质（下面提到的区间都是可由子区间合并而来的，即值非0）：

• 对于区间$[l, r]$，合并后区间$[l, r]$的值必为原输入中的$[l, r]$段之和。因为区间和一定，所以区间越长，区间值越大。

• 确定一个左端点$l$，那么对于右端点$r1 < r2 < r3 < ...$，有$[l, r1] < [l, r2] < [l, r3] < ...$，即区间值具有单调性。确定右端点同理。

所以，我们可以得到以下结论与方案：

• 在一个区间内，只要找到一种满足题目要求的合并方案，就可确定这段区间的值。可以以此减少循环次数。

• 在合并三个饭团时，若枚举到的中间区间为$[k, t]$，随着$k$与$t$向中间靠近，$[l, k - 1]$与$[t + 1, r]$逐渐增大。可以使用双指针，减少一层循环。

于是本题得解，时间复杂度$O(N^3)$。

#include <bits/stdc++.h>
using namespace std;

int n, f[500][500], ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> f[i][i];
        ans = max(ans, f[i][i]);
    }

    for (int len = 2; len <= n; ++len) {
        for (int l = 1, r = len; r <= n; ++l, ++r) {
            // 两个合并
            for (int k = l; k < r; ++k) {
                if (f[l][k] && f[k + 1][r] && f[l][k] == f[k + 1][r]) {
                    f[l][r] = f[l][k] + f[k + 1][r];
                    break;
                }
            }

            // 双指针，三个合并
            for (int k = l, t = r; k < t - 1; ) {
                if (f[l][r]) break;
                if (!f[l][k]) ++k;
                else if (!f[t][r]) --t;
                else if (f[l][k] == f[t][r]) {
                    if (f[k + 1][t - 1])
                        f[l][r] = f[l][k] + f[k + 1][t - 1] + f[t][r];
                    else ++k, --t;
                }
                else if (f[l][k] < f[t][r]) ++k;
                else if (f[l][k] > f[t][r]) --t;
            }
            ans = max(ans, f[l][r]);
        }
    }

    cout << ans << endl;
    return 0;
}