思路与算法

合并每次令长度减少k-1，所以原长len的区间最终剩余t=(len-1) mod(k-1)+1个字符。DP[l][r][mask]记录它缩成t位串的最大收益。按长度递增，枚举最后一个剩余字符的来源后缀，前段提供t-1位；当t=1时前段提供k-1位，拼成k位后应用规则，得到新一位并加分。

正确性说明

合并始终保持每个剩余字符对应连续原区间。最终若剩t>1位，按最后一位来源切分可唯一表达为两段各自完成，枚举覆盖所有情况；t=1且非单字符时，最后一步必合并k个已缩成字符的连续块，同样分解前k-1位及最后一位即可。转移反向执行合法，长度递增保证依赖已完成。分数均正，剩余≥k时继续操作必增益，故最终必须缩到t位。

复杂度

粗上界O(n³2^k)时间，实际分割间隔k-1且每区间只存其唯一t位状态。空间O(n²2^(k-1))上界，实际按t变长分配；初始化同存储量。n≤300,k≤8，收益用64位。

易错点

规则有2^k条且从全0模式开始，公开样例可验证。不能只存缩成0或1的区间而忽略k>2时的多位残留。NEG标记不可达，不让它参与加分。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n), c(1 << k);
    vector<ll> w(1 << k);
    for (int &x : a)
        cin >> x;
    for (int i = 0; i < (1 << k); i++)
        cin >> c[i] >> w[i];
    const ll NEG = -(1LL << 60);
    vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(n));
    for (int len = 1; len <= n; len++) {
        int t = (len - 1) % (k - 1) + 1;
        for (int l = 0; l + len <= n; l++) {
            int r = l + len - 1;
            auto &out = dp[l][r];
            out.assign(1 << t, NEG);
            if (len == 1) {
                out[a[l]] = 0;
                continue;
            }
            for (int mid = r - 1; mid >= l; mid -= k - 1) {
                auto &left = dp[l][mid];
                auto &right = dp[mid + 1][r];
                for (int mask = 0; mask < (int)left.size(); mask++)
                    if (left[mask] != NEG)
                        for (int b = 0; b < 2; b++)
                            if (right[b] != NEG) {
                                int z = (mask << 1) | b;
                                ll v = left[mask] + right[b];
                                if (t == 1)
                                    out[c[z]] = max(out[c[z]], v + w[z]);
                                else
                                    out[z] = max(out[z], v);
                            }
            }
        }
    }
    cout << *max_element(dp[0][n - 1].begin(), dp[0][n - 1].end()) << '\n';
}