题解 P4805 【[CCC 2016]合并饭团】

kai586123 · 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;
}