------------
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 250;
int f[N][N];
int main() {
int n, ans = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", f[i] + i);
ans = max(ans, f[i][i]);
}
for(int len = 2; len <= n; len++)
for(int l = 1; l +len -1 <= n; l++) {
int r = l + len - 1;
for(int k = l; k < r; k++)
if(f[l][k] == f[k + 1][r] && f[l][k]) {
f[l][r] = max(f[l][r], f[l][k] + 1);
ans = max(ans, f[l][r]);
}
}
printf("%d\n", ans);
return 0;
}
```
上面代码的时间复杂度为$O(N^3)$（~~应该是吧~~）
看完上面那些，相必你对区间$DP$有了更深一层的了解。
我们可以把区间$DP$进行一些总结：
1. 区间合并性
1. 注意转移条件
其余和普通$DP$应该时差不多的了。
------------
### **难道你以为这一题就完了？**
**不，这一题还有其他$DP$做法。**（我也不知道叫啥）
定义状态$f[i][k]$，表示第$i$个数合并得到数值为$k$，能够向右拓展的最右端点。因为是最右端点，所以这个$k$也一定是最大的。
那么我们怎么转移？我们学过线性$DP$应该都清楚。这次合并的价值是$+1$，那么上一次就是$k-1$，上一次的右端点就是$f[i][k-1]$，那么只要$f[i][k]$为$0$，即还没取到最优值，我们就可以转移：
$$f[i][k]=f[f[i][k-1]][k-1],if:f[i][k]=0$$
这个方程是比较难想的，也是比较复杂的，需要多思考。
那么如果$f[i][k]$不为$0$，说明数值$k$是可以合并到的，那么我们只需更新答案：
$$ans=max(ans,k),if:f[i][k]>0$$
我们枚举$k$即可。
**但是哪一层循环放外面呢？我们应该要清楚，这里的$k$才是阶段，而$1-n$那一层才是决策。**
**那么$k$最大是多少，最小又是多少**？我们来看$N∈[2,248]$，每一个数值$∈[1,40]$，那么$k$最大的情况就是$N=248$，所有数值都等于$40$，可以算出$k_{max}=47$，而最小呢？我们依次类推，$k_{min}=1$，即整个数列$N=1$，只有一个数$1$的情况。
转移边界:对于每一个数列的数值$a[i]$，$f[i][a[i]]=i+1$，即其最多向右合并到$i+1$。这个需要好好理解。
这样的$DP$基于倍增思想（我也不太清楚，~~倍增写得少~~）
$Code:
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 250, K = 50;
int f[N][K];
int main() {
int n, x, ans = 0;
scanf("%d", &n);
for(int i = 1;i <= n; i++) {
scanf("%d", &x);
f[i][x] = i + 1;
ans = max(ans, x);
}
for(int k = 1;k <= 47; k++)
for(int i = 1; i <= n; i++) {
if (f[i][k] == 0)
f[i][k] = f[f[i][k - 1]][k - 1];
if (f[i][k])
ans=max(ans, k);
}
printf("%d\n", ans);
return 0;
}