A

题目链接

核心思路：这很明显是一道区间dp板子题

集合定义：\(f[i][j]表示的是将序列的第i个数合并到第j个数\)全部合并所能得到的最大值。

集合划分：和石子合并的区间划分是一样的哦，先枚举长度，然后枚举左端点那么右端点也就确定了。然后我们再对区间里进行划分，这就是\(f[i][j]\)的子集。要注意有些状态是不合法的哦，划分的左右区间合并之后的是相等的才是合法的状态，也就是\(f[l][k]==f[k+1][r]\).

状态转移方程：

\(f[i][j]=max(f[i][j],f[i][k]+1)\).其中\(f[i][k]+1\)是因为这是题目要求的，需要我们两个相等的合并之后就是左区间或者是右区间的加1.

这里有个处理得比较好的地方就是f数组的储存，可以查看内存看一下。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 3e2 + 10;
int f[N][N];

int n;
int main()
{
	int n;
	int ans = 0;
	cin >> 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]);
				}
			}
		}
	}
	cout << ans << endl;
}