526互联

B - 248 G

发布时间 2023-08-09 19:42:52作者: yabnto

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;
}