思路
本题为 P3146 变式，也算是一道很经典的区间 DP 题了。
因为 \(n \leq 500\)，考虑区间 DP。定义 \(dp_{i,j}\) 表示操作 \([i,j]\) 区间剩余长度的最小值。
那么，我们可以枚举一个中间值 \(k\)，可以显然地得到一个状态转移方程（即不能合二为一的情况）：
\[ dp_{i,j} = \min(dp_{i,k} + dp_{k + 1,j}) \]然后，我们再来考虑两个区间能够合并的情况。
如果 \([i,k]\) 和 \([k + 1,j]\) 能合并，当且仅当 \(dp_{i,k} = dp_{k + 1,j} = 1\)，以及两段区间合并出的值相同。
但是，我们现在并不知道两段区间的值具体是多少。所以，现在有两种处理方式：
- 将合并区间得到的值作为 \(dp\) 的一维用来枚举，但这显然是不行的，因为时间复杂度将变为 \(\Theta(n^3m)\)。（其中 \(m = \max\{a_i\}\)。）
- 再开一个数组 \(f\) 记录两个区间的合并后的值。
那么，对于这个问题显然只能选择第二种方案。
由此，不妨令 \(f_{i,j}\) 表示合并 \([i,j]\) 区间得到的数值。那么，我们就可以在处理 \(dp_{i,j}\) 的时候同时更新 \(f_{i,j}\)。
综上，对于 \([i,k]\) 和 \([k + 1,j]\) 能合并，需满足：
\[ dp_{i,k} = dp_{k + 1,j} = 1 \wedge f_{i,k} = f_{k + 1,j} \]时间复杂度：\(\Theta(n^3)\)。
Code
#include <bits/stdc++.h>
#define re register
using namespace std;
const int N = 510,inf = 0x3f3f3f3f;
int n,ans = inf;
int arr[N];
int f[N][N],dp[N][N];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
int main(){
memset(dp,inf,sizeof(dp));
n = read();
for (re int i = 1;i <= n;i++) arr[i] = read();
for (re int i = 1;i <= n;i++){
f[i][i] = arr[i];
dp[i][i] = 1;
}
for (re int l = 1;l <= n;l++){
for (re int i = 1;i + l - 1 <= n;i++){
int j = i + l - 1;
for (re int k = i;k < j;k++){
dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + 1][j]);//不合并
if (dp[i][k] == dp[k + 1][j] && dp[i][k] == 1 && f[i][k] == f[k + 1][j]){//满足条件，说明两区间可以合并
dp[i][j] = min(dp[i][j],dp[i][k]);//更新两个 DP 数值
f[i][j] = f[i][k] + 1;
}
}
}
}
printf("%d",dp[1][n]);
return 0;
}