P4805 题解 最后更新于 2025-05-02 00:00:26

## 题意 $n$ 个饭团，每个饭团大小为 $a_i$ ，每次合并可以合并两个相邻的大小相等的饭团，也可以合并两个中间相隔一个饭团的大小相等的饭团。求合并完成后最大的饭团的大小的最大值。 $n\le 400$ ## 思路 显然是区间dp。合并相邻两个就是石子合并，不再展开说。研究三个合并。 我们可以枚举中间那个饭团的左右端点，暴力合并。这样做是 $O(n^4)$ 的。考虑到要使两边相等，可以双指针，初始时一个指向最左，一个指向最右。通过两个指针不断地向内靠拢实现转移。时间复杂度 $O(n^3)$ 。 这题数据也是弱到一定地步了， $O(n^4)$ 暴力随便卡卡都能过，~~这谁还想写正解啊~~。