题目大意

有 $N$ 个饭团排成一行，可以进行两种合并操作：

合并两个相邻且大小相同的饭团

合并两个大小相同且中间隔一个饭团的饭团（中间饭团大小任意）

可以执行任意次操作，求能得到的最大饭团大小。

算法思路

核心思想

区间动态规划，判断每个区间能否合并成一个饭团。

关键定义

sum[i]：前 $i$ 个饭团的大小前缀和

f[l][r]：区间 $[l, r]$ 能否合并成一个饭团

str(l, r)：区间 $[l, r]$ 内饭团大小总和

状态转移

情况1：分成两个区间合并

如果存在 $k \in [l, r-1]$ 使得：

str(l, k) == str(k+1, r)（两个区间总和相等）

f[l][k] == true 且 f[k+1][r] == true（两个区间各自可合并）

则 f[l][r] = true

情况2：三个区间合并（中间夹一个）

如果存在 $k, kk$ 满足 $l \le k < kk \le r$ 且 $k + 1 < kk$ 使得：

str(l, k) == str(kk, r)（左右两端区间总和相等）

f[l][k] == true 且 f[kk][r] == true 且 f[k+1][kk-1] == true

则 f[l][r] = true

双指针优化 对于情况2，使用双指针技巧高效寻找满足条件的 $k$ 和 $kk$：

初始化 $k = l$, $kk = r$

根据左右区间和的大小关系移动指针

算法流程

读入数据，计算前缀和

初始化：单个饭团 f[i][i] = true

按区间长度从小到大进行DP：

枚举所有可能的划分点

检查两种合并情况

遍历所有区间，找出可合并区间中的最大和

复杂度分析

时间复杂度：$O(N^3)$，但双指针优化后常数较小

空间复杂度：$O(N^2)$，存储DP状态

总结

本题是区间DP的典型应用：

区间划分：考虑所有可能的区间划分方式

状态设计：f[l][r] 表示区间能否合并

双指针优化：高效处理三区间合并的情况

前缀和：快速计算区间和

这种"区间DP + 双指针"的方法适用于许多区间合并类问题，特别是在需要检查多种合并方式时非常有效。