组队打 *CPC 的题，不知道独立能不能做出来。

题目链接

有 个元素，第 个元素的初始类型为 ，等级为 ；第 种类型的牌的权值为 。

可以进行两种操作若干次（ 为给定常数）：

1. 选择一个元素，假设其类型为 ，等级为 ，删掉这个元素，代价加 。
2. 选择相邻两个类型相同的元素，设其类型均为 ，等级均为 且小于 ，删掉这两个元素，在原位置加入一个类型为 ，等级为 的新元素。

求最大代价。

• 多测，；
• ；
• ；
• ；
• 。

---

首先一眼区间 DP 啊，考虑状态如何设计方便合并。

由于合并时挑选两个相同类型相同等级的元素，因此我们考虑在状态中维护当前区间剩下唯一元素，其类型为 ，等级为 时的最大代价。

顺便，维护将一个区间全部删除后的最大代价。

假设 表示在区间 中，只剩下一个类型为 且等级为 的元素时的最大代价，设 为将区间全部删除后的最大代价。

初始状态的设定为

其余未指定的状态设为 。

显然有以下的转移方程，方便表述，这里假定 的含义为将 的值赋为 。

因此时间复杂度为单组测试 的，这个计算量看似是 的，乘上多测次数 ，似乎难以通过。

不过，我们注意到，只有合并两个元素才可以使元素等级升一级，而数据范围保证最多只有 个元素，显然最多升级 次到 级，因此 在估算计算量时应取 （或者我们说，时间复杂度实际上是 ），此时计算量估计大概降到 。

实际上，DP 代码可能比大多数人想象的常数都来的小，并且本题转移 DP 时 的计算量来自枚举 ，后者实际上还有一个 的常数。

这样乘上多测的计算量估计大约为 ，原题有 ，通过本题绰绰有余了。

#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

static constexpr int64_t i64min = numeric_limits<int64_t>::min() >> 2;

void solve() {
  size_t n, m, r;
  int64_t p;
  cin >> n >> m >> r >> p;
  r = min(r, (size_t)8);

  vector<vector<int64_t>> G(n, vector<int64_t>(n, 0));
  vector<vector<vector<vector<int64_t>>>> F(n, vector<vector<vector<int64_t>>>(n, vector<vector<int64_t>>(m, vector<int64_t>(r, i64min))));

  vector<int64_t> powp(r);
  powp[0] = 1;
  for (size_t i = 1; i < r; ++i)
    powp[i] = powp[i - 1] * p;

  vector<size_t> a(n);
  for (size_t i = 0; i < n; ++i)
    cin >> a[i], --a[i];

  vector<int64_t> v(m);
  for (size_t i = 0; i < m; ++i)
    cin >> v[i];

  for (size_t i = 0; i < n; ++i)
    for (size_t j = 0; j < n; ++j) {
      for (size_t k = 0; k < m; ++k)
        for (size_t l = 0; l < r; ++l)
          F[i][j][k][l] = i64min;
      G[i][j] = 0;
    }

  for (size_t i = 0; i < n; ++i)
    F[i][i][a[i]][0] = 0, G[i][i] = v[a[i]];

  for (size_t len = 1; len <= n; ++len) {
    for (size_t i = 0, j = len; j < n; ++i, ++j) {
      for (size_t h = i; h < j; ++h)
        G[i][j] = max(G[i][j], G[i][h] + G[h + 1][j]);
      for (size_t k = 0; k < m; ++k) {
        for (size_t l = 0; l < r; ++l) {
          for (size_t h = i; h < j; ++h)
            F[i][j][k][l] = max(F[i][j][k][l], max(F[i][h][k][l] + G[h + 1][j], G[i][h] + F[h + 1][j][k][l]));
          if (l != 0)
            for (size_t h = i; h < j; ++h)
              F[i][j][k][l] = max(F[i][j][k][l], F[i][h][k][l - 1] + F[h + 1][j][k][l - 1]);
          G[i][j] = max(G[i][j], F[i][j][k][l] + v[k] * powp[l]);
        }
      }
    }
  }
  cout << G[0][n - 1] << '\n';
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  size_t T;
  cin >> T;
  while (T--)
    solve();
  return 0;
}