B - 248 G
题意
给定一个长度为 \(N\) 的数列 \(a_1,\ a_2,\ \dots , a_N\) ，你可以任意次进行如下操作：
- 选择数列中两个相邻且相等的元素。删去其中一个元素并使另一个元素的值 \(+1\) 。
问在最优策略下，数次操作后数列中的最大值可以是多少。
思路
区间 dp。
先考虑 DFS 怎么做，对于一个序列，搜索他如何分裂在组合，然后再在回溯时统计答案，那么可以将代码变成一种分治，然后区间 dp。
code
点击查看代码
#include <iostream>
using namespace std;
const int MaxN = 258;
int dp[MaxN][MaxN], n, ans;
int main() {
//freopen("248.in", "r", stdin);
//freopen("248.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
fill(dp[1], dp[n + 1], -1);
for (int i = 1; i <= n; i++) {
cin >> dp[i][i], ans = max(ans, dp[i][i]);
}
for (int len = 2; len <= n; len++) {
for (int i = 1, j = i + len - 1; j <= n; i++, j++) {
for (int k = i; k < j; k++) {
if (dp[i][k] == dp[k + 1][j]) {
dp[i][j] = max(dp[i][j], dp[i][k] + 1);
}
}
ans = max(ans, dp[i][j]);
}
}
cout << ans << endl;
return 0;
}