分析

挺有启发意义的题目。

第一眼看上去像一个套路的区间 DP，但是区间想要合并必须满足值相等。

考虑设 \(g(i,j)\) 为区间 \([i,j]\) 最终合并成的值，如果不能合并为 \(1\) 个元素，那么为 \(-1\)。

设 \(f(i)\) 为以 \(i\) 结尾的序列，能够划分的最短长度。 \[ f(i) = \min_{g(j,i) > 0}\{ f(j-1) + 1\} \] \(j\) 实际上是个断点。

而 \(g(i,j)\) 可以用类似于区间 DP 的方式实现。

线性 DP 套一个区间 DP。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=505;
int n, a[N], f[N], g[N][N];
int dp(int i,int j) {
	if(g[i][j]) return g[i][j];
	if(i==j) return g[i][j]=a[i];
	int& x=g[i][j];
	x=-1;
	for(int k=i;k<j;++k) {
		int p=dp(i,k), q=dp(k+1,j);
		if(p>0&&p==q) return x=p+1;
	}
	return x;
}
signed main() {
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	memset(f,0x3f,sizeof(f));
	f[0]=0, f[1]=1;
	for(int i=2;i<=n;++i) {
		for(int j=1;j<=i;++j) {
			if(dp(j,i)>0) f[i]=min(f[i],f[j-1]+1);
// 			printf("kkk=[%lld,%lld]\n",i,j);
		}
	}
	printf("%lld\n",f[n]);
}