题面

链接：https://www.nowcoder.com/questionTerminal/5c9c7ea6f692438693a944962a3f71d8?answerType=1&f=discussion
来源：牛客网

外卖节即将过去了，小美还有很代金券没有消费掉，美团面向小美这样的用户推出了一个新的活动，即代金券消消乐活动。系统会把小美的代金券打乱顺序排成一排，小美可以进行任意多次如下操作：

如果存在相邻的两个代金券金额相等,设其面额为x，小美可以使用这两张代金券换一张面额为x+1的代金券，并将其仍放在原来两张券的位置上，每进行一次这样的操作，小美就可以获得1元可以无限期使用的奖励金。

小美觉得奖励金可太香了，因此她想获得尽可能多的奖励金，请问她最多可以获得多少奖励金。

输入描述:
输入第一行仅包含一个正整数n，表示小美拥有的代金券数量。(1<=n<=500)

输入第二行包含n个正整数，每个整数x表示一张代金券的面额，同时这也是系统排出的代金券顺序。(1<=x<=100)

输出描述:
输出仅包含一个整数，表示小美最多可以获得的奖励金数量。

示例1
输入
5
1 1 1 1 1
输出
3
说明
{1,1,1,1,1}->{1,1,1,2}->{1,2,2}->{1,3}

解析

• dp[st][ed]表示[st,ed]这一段区间能够合并成的最小长度
• w[st][ed]表示若[st,ed]这一段区间能合并成一段，这一段的值是多少
• ans[st][ed]表示[st,ed]这一段区间通过合并能够带来的最大贡献
  枚举分界点k，有转移方程：

dp[st][ed] = min(dp[st][ed], dp[st][k] + dp[k + 1][ed]);
ans[st][ed] = max(ans[st][ed], ans[st][k] + ans[k + 1][ed]);
if (dp[st][k] == 1 && dp[k + 1][ed] == 1 && w[st][k] == w[k + 1][ed]) {
  dp[st][ed] = 1;
  w[st][ed] = w[st][k] + 1;
  ans[st][ed] = max(ans[st][ed], ans[st][k] + ans[k + 1][ed] + 1);
}

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<vector<int>> dp(n + 1, vector<int>(n + 1, (int)1e9));
  vector<vector<int>> w(n + 1, vector<int>(n + 1));
  vector<vector<int>> ans(n + 1, vector<int>(n + 1));
  for (int i = 1; i <= n; i++) cin >> w[i][i], dp[i][i] = 1;
  for (int len = 2; len <= n; len++) {
    for (int st = 1; st + len - 1 <= n; st++) {
      int ed = st + len - 1;
      for (int k = st; k < ed; k++) {
        dp[st][ed] = min(dp[st][ed], dp[st][k] + dp[k + 1][ed]);
        ans[st][ed] = max(ans[st][ed], ans[st][k] + ans[k + 1][ed]);
        if (dp[st][k] == 1 && dp[k + 1][ed] == 1 && w[st][k] == w[k + 1][ed]) {
          dp[st][ed] = 1;
          w[st][ed] = w[st][k] + 1;
          ans[st][ed] = max(ans[st][ed], ans[st][k] + ans[k + 1][ed] + 1);
        }
      }
    }
  }
  cout << ans[1][n];
  return 0;
}