注：两道题目题意是一样的，但是数据范围不同，一个为弱化版，另一个为强化版。
P3146传送门（弱化版）
思路：
区间动规，设 f [ i ][ j ] 表示在区间 i ~ j 中获得的最大值，与普通区间动规最大的不同在于：只有左区间的最大值等于右区间的最大值时才能够进行转移。
AC代码：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define maxn 257
int n;
int maxx=-0x3f;//maxx记录合并后的最大值
int f[maxn][maxn];//f[i][j]表示 i~j 区间内合并后的最大值
inline int read()
{
char kr=;
char ls;
for(;ls>''||ls<'';kr=ls,ls=getchar());
int xs=;
for(;ls>=''&&ls<='';ls=getchar())
{
xs=xs*+ls-;
}
if(kr=='-') xs=-xs;
return xs;
}
int main()
{
n=read();
for(int i=;i<=n;i++)
{
f[i][i]=read();
maxx=max(f[i][i],maxx);
}
for(int i=;i<=n;i++)// i 枚举区间长度
{
for(int j=;j+i-<=n;j++)//枚举左端点
{
int r=i+j-;//计算出右端点
for(int k=j;k<r;k++)//枚举断点
{
if(f[j][k]==f[k+][r])//如果断点的左右两边最大值相等，转移
{
f[j][r]=max(f[j][r],f[j][k]+);
maxx=max(maxx,f[j][r]);//记录最大值
}
}
}
}
printf("%d\n",maxx);//输出
return ;
}
P3147传送门（强化版）
思路：
在数据范围 2~262144 的情况下，使用区间动规在空间和时间上就有点吃不消了。这是我们考虑更加优化的动规，可以设 f [ i ][ j ] 表示从 j 开始合并到 i 这个数字序列的末尾的下标是什么。那么因为合并的总是一段连续的区间，就有 f [ i ][ j ] = f [ i-1 ][ f [ i-1 ][ j ] ];
AC代码：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define maxn 300000
int n,a;
int ans=-0x3f;
int f[][maxn];
inline int read()
{
char kr=;
char ls;
for(;ls>''||ls<'';kr=ls,ls=getchar());
int xs=;
for(;ls>=''&&ls<='';ls=getchar())
{
xs=(xs<<)+(xs<<)+ls-;
}
if(kr=='-') xs=-xs;
return xs;
}
int main()
{
n=read();
for(int i=;i<=n;i++)
{
a=read();
f[a][i]=i+;
}
for(int i=;i<=;i++)
{
for(int j=;j<=n;j++)
{
if(!f[i][j]) f[i][j]=f[i-][f[i-][j]];
if(f[i][j]) ans=i;
}
}
printf("%d\n",ans);
return ;
}