(dp[l][r]:=) 区间([l,r])全部合并时可得到的最大数字。
由题意可以推出状态转移方程(注意新的数值是原来的数值+1):
[dp[l][r]=max(dp[l][r],dp[l][k]+1)
]
注意,只有相邻且数字相同的两个格子才能合并,因此转移的前提是(dp[l][k]==dp[k+1][r])
由上可见本题与“石子合并”不同,状态转移是有前提的。故(dp[l][r])的定义强调“全部合并”,因此一些(dp)值可能因为不满足条件而无法更新,因此答案不一定为(dp[1][n])。应该扫一遍(dp)数组取其中的最大值。这个过程可以直接放在状态转移的代码之后,(ans)比较一下新(dp)值即可,详见代码。
int main()
{
//ios::sync_with_stdio(false);
//while (scanf("%d%d",&n,&m)!=EOF){
int N; cin >> N;
for (int i = 1; i <= N; i++) {
cin >> a[i];
dp[i][i] = a[i];
}
int ans = 0;
for (int len = 2; len <= N; len++) {
//枚举长度
for (int l = 1; l <= N - len + 1; l++) {
//枚举左端点l
int r = l + len - 1;
for (int spl = l; spl <= r - 1; spl++) {
//枚举分割点split
//表示在spl堆与spl+1堆之间分割
if (dp[l][spl] == dp[spl + 1][r]) {
dp[l][r] = max(dp[l][r], dp[l][spl] + 1);
ans = max(ans, dp[l][spl] + 1);
}
}
}
}
cout << ans;
return 0;
}