P3146 [USACO16OPEN]248 题解
# 非常不错的一道区间DP题
如果您对区间DP还不是很了解，建议先尝试下“石子合并”这道差不多是模板的题，这里给出链接：石子合并
在您对了区间DP有了一定的了解之后，我们开始讲解这道题：
现在我们对这道题进行初步的分析：
1.此题为序列上的操作
2.只有相邻的两个数字相同才能进行合并，且合并后得到的数是由原数加上1后得到的
现在，我们在考虑这道为什么要用区间DP来解决：
1.最终的状态是由一个个较小的状态转移过来的
2.区间DP更容易判断可以进行合并的情况
综上所述,这道题的整体思路如下：
用f[i][j]表示将序列中的第i个数合并到第j个数全部合并所能得到的最大数值
状态转移方程如下：
if(f[i][pos] == f[pos+1][j])
{
f[i][j] = max(f[i][j], f[i][pos] + 1);
ans = max(ans, f[i][pos] + 1);
}其中ans为最终答案，只有当左边的部分和右边的部分的数值相同时才能进行转移。
为什么当f[i][pos] !=f[pos+1][j]时，不能进行f[i][j]=max(f[i][pos],f[pos+1][j])的转移呢？
我们看f数组的定义，其中特别提到了“完全合并”
所以不能完全合并的话就不能进行转移
比如说，你有“7 5 7” 这么一个合并后的东西，显然这两个“7”无法合并，但如果你在转移时将“5”和“7”转移成了“7”，你的下一步中两个“7”就变的可以合并了，就会出错。
这也就解释了为什么f[1][n]并不一定是最终答案，因为从1到n并不一定能全部合并，即f[1][n]有可能是0，所以在下面的代码中的转移过程中就进行取最终答案的操作 （之前在此处少写了一句话，本次纠正）。
下面放代码：
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 255;
int n, val, ans;
int f[maxn][maxn];
inline int read(void) // 快读优化
{
int s = 0, w = 1;
char ch = getchar();
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') w = -1;
for(; ch <= '9' && ch >= '0'; ch = getchar()) s= s * 10 + ch - '0';
return s * w;
}
int main()
{
n = read();
for(register int i = 1; i <= n; i++) val = read(), f[i][i] = val; // 预处理，当不进行合并时得到的价值就是自己
for(register int len = 2; len <= n; len++) // 枚举所合并区间的长度，因为转移是从小区间转移到大区间，所以要从小到大枚举区间的长度
{
for(register int i = 1; i <= n - len + 1; i++) // 枚举区间的左端点 ，当左端点等于 全长 减去 区间长度 再加一 的时候，右端点取到序列的最右边
{
int j = i + len - 1;
for(register int pos = i; pos < j; pos++) // 枚举当前区间可以由哪两个小区间转移过来
{
if(f[i][pos] == f[pos+1][j] && f[i][pos] != 0 && f[pos+1][j] != 0) // 如果这两个小区间合并出的值相等，就进行转移 ，特别地，如果两个的值都是0，表示这两个区间什么也合并不出来，所以不能进行转移
{
f[i][j] = max(f[i][j], f[i][pos] + 1);
ans = max(ans, f[i][pos] + 1); // 用ans来保存答案
//cout<< f[i][pos] << ' ' << f[pos+1][j] << '\n'; 调试用
}
}
}
}
cout << ans << '\n';
return 0;
}讲解就到此结束了，有问题的话发评论或私信都可以。