题目链接：https://www.luogu.com.cn/problem/P3146
这题一开始我想的状态是f[i][j]表示从i合并到j的最大值
方程就是如果f[i][l]=f[l+1][j]，f[i][j]=max(f[i][j],f[i][l]+1);否则f[i][j]=max(f[i][j],max(f[i][l],f[l+1][j]))；
但这是不对的，因为后面一个式子可能导致f[i][j]得出了一个值，但这个值是从子区间里选的，即使f[i][j]和某个区间相等也不一定能合并。
举个例子：3 1 2 2-->3 1 3是正确的合并，答案为3，但方程会这样执行： 3 1 2 2-->3 1 3-->3 3-->4
于是又沙雕的开了一个数组v，v[i][j]=1表示能从i合并到j，v[i][j]=0表示不能，每次合并前先判断一下子区间的v是不是为1。脑补一下感觉问题不大，实际上也过了。
贴个代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=250+10;
int f[maxn][maxn],v[maxn][maxn],a[maxn];
int n,i,j,k,t,m,l;
int main(){
cin>>n;
for (i=1;i<=n;i++) cin>>a[i];
memset(f,0,sizeof(f));memset(v,0,sizeof(v));
for (i=1;i<=n;i++) {
f[i][i]=a[i];v[i][i]=1;
}
for (k=1;k<=n-1;k++) //***
for (i=1;i<=n-1;i++)
if (i+k<=n){
j=i+k;
for (l=i;l<=j-1;l++)
if (v[i][l]==1&&v[l+1][j]==1){ //若都是完全合并，则分为两堆相等和两堆不等
if (f[i][l]==f[l+1][j]){
if (f[i][l]+1>=f[i][j]){
f[i][j]=f[i][l]+1;v[i][j]=1;
}
}
else{
m=max(f[i][l],f[l+1][j]);
if (m>f[i][j]){
f[i][j]=m;v[i][j]=0;
}
}
}
else{ //如果不都是完全合并
m=max(f[i][l],f[l+1][j]);
if (m>f[i][j]){
f[i][j]=m;v[i][j]=0;
}
}
}
cout<<f[1][n]<<endl;
return 0;
}
后来在洛谷上看题解时，看到一种更好的状态，是f[i][j]表示从i合并到j且全部合并，能得到的最大值。因此f[i][j]可以为0（i到j不能全部合并）
转移方程：若f[i][l]=f[l+1][j]（l为分割点），f[i][j]=max(f[i][l]+1,f[i][j])，并同时更新答案ans=max(ans,f[i][j])。
贴个代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=250+10;
int a[maxn],f[maxn][maxn]; //f[i][j]表示将i~j *全部* 合并能得到的最大值
int n,i,j,k,ans,l;
int main(){
cin>>n;
ans=0;memset(f,0,sizeof(f));
for (i=1;i<=n;i++){
cin>>a[i];f[i][i]=a[i];
ans=max(ans,a[i]);
}
for (k=1;k<=n-1;k++)
for (i=1;i<=n-1;i++)
if (i+k<=n){
j=i+k;
for (l=i;l<=j-1;l++)
if (f[i][l]==f[l+1][j]&&f[i][l]!=0&&f[l+1][j]!=0){ //若f[i][l]=0；说明区间[i,l]不能全部合并，f[i+1][j]同理
f[i][j]=max(f[i][j],f[i][l]+1);
ans=max(ans,f[i][j]); //随时更新答案，因为答案不一定为f[1][n]
}
}
cout<<ans<<endl;
return 0;
}
原文：https://www.cnblogs.com/edmunds/p/12512402.html