原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：求操作完毕序列中的最大值
1.2 题目背景、允许、禁止与限制
背景：有一个有 nnn 个数的序列
允许：选择两个相邻且相等的数，替换为比原数 +1+1+1 的数
1.3 题目数据范围与猜测
2≤n≤248⟶O(n3)2 \le n \le 248 \longrightarrow O(n^3)2≤n≤248⟶O(n3)
1.4 一句话概括题意
有一个序列，每次可以选择两个相邻且相等的数，替换为比原数 +1+1+1 的数。最终求操作完毕后的序列最大值。
2 题目破题推导
2.1 第一步：以终为始、以始为终
两个相邻的数（这里的一个数不仅包括单独的一个数，更包括一段区间合并后得到的数）能合并
当且仅当：
* 左右两边都能完成合并
* 左边合并结果 === 右边合并结果
也就是说，对于一个大区间 [left,right][left,right][left,right]，中间有断点 i(left≤i≤right)i(left\le i \le right)i(left≤i≤right)，区间 [left,i][left,i][left,i] 和 [i+1,right][i+1,right][i+1,right]能合并，当且仅当 [left,i]=[i+1,right][left,i] = [i+1,right][left,i]=[i+1,right] 并且 [left,i][left,i][left,i] 与
[i+1,right][i+1,right][i+1,right] 均可以合并
3 模型匹配
先提取关键词：时刻求取当前最大值、区间
是 区间动态规划\huge{区间动态规划}区间动态规划
4 具体方案
4.1 动态规划定义（重点）
首先，先建立 dp 数组
设置 dpij{dp_i}_jdpi j 表示把区间 [i,j][i,j][i,j] 完全合并成一个数得到的最大值是什么
000 代表区间 [i,j][i,j][i,j] 无法完全合并
4.2 初始化
求最大值，所以dp数组每一项都设为小值
但是一个数不用合并，因此对于每个 i(1≤i≤n)i (1 \le i \le n)i(1≤i≤n)，都要将 dpii{dp_i}_idpi i 设置为 序列i序列_i序列i
4.3 状态转移方程
4.4 答案求取
对于所有 i(1≤i≤n),j(1≤j≤n)且i≤j,求dpiji(1 \le i \le n),j(1 \le j \le n) 且 i\le j,求{dp_i}_ji(1≤i≤n),j(1≤j≤n)且i≤j,求dpi j 的最大值
5 最终代码（禁止抄袭，仅用于参考）
