Solution

一眼区间 DP。然后很快想到了一个 $O(n^3 \times 2^k)$ 的做法：设 $dp_{l,r,st}$ 为区间 $[l,r]$ 中的数全部合并为 $st$ 状态的最大权值。转移的时候找到后缀的区间，把它压成一个数。

但是很显然通过不了。我们寻求优化。

第一点，我们发现，一个区间再怎么合并，它的长度和原长必定模 $k-1$ 同余。因此后缀区间只需枚举原来的 $\frac{1}{k}$。

再发现，我们整个区间，长度基本上是模 $k-1$ 均匀分布的。（我是说基本上，差异在 $O(k)$ 量级内）因此我们发现，$\frac{1}{k} \sum_{i=1}^{k} 2^i = \frac{2^{k+1}}{k}$，基本上又把一个东西的枚举量除了 $k$。

因此我们就用这个非常简单的优化就可以做到 $O(\frac{n^3 \times 2^k}{k^2})$，应该也许能过吧。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=300+10,MAXK=(1<<8)+10;
int n,k,a[MAXN],dp[MAXN][MAXN][MAXK],nxt[MAXK],w[MAXK];
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k; ffor(i,1,n) cin>>a[i]; ffor(i,0,(1<<k)-1) cin>>nxt[i]>>w[i];
	memset(dp,-0x3f,sizeof(dp)); ffor(i,1,n) dp[i][i][a[i]]=0;
	ffor(len,2,n) {
		for(int l=1,r=len;r<=n;l++,r++) {
			ffor(j,l,r-1) if((r-j)%(k-1)==1%(k-1)) {
				if(dp[j+1][r][0]>=0) {
					ffor(st,0,(1<<((j-l)%(k-1)+1))-1) {
						int ST=(st<<1);
						if((j-l)%(k-1)+2==k) dp[l][r][nxt[ST]]=max(dp[l][r][nxt[ST]],dp[l][j][st]+dp[j+1][r][0]+w[ST]);
						else dp[l][r][ST]=max(dp[l][r][ST],dp[l][j][st]+dp[j+1][r][0]);
					}
				}
				if(dp[j+1][r][1]>=0) {
					ffor(st,0,(1<<((j-l)%(k-1)+1))-1) {
						int ST=(st<<1)+1;
						if((j-l)%(k-1)+2==k) dp[l][r][nxt[ST]]=max(dp[l][r][nxt[ST]],dp[l][j][st]+dp[j+1][r][1]+w[ST]);
						else dp[l][r][ST]=max(dp[l][r][ST],dp[l][j][st]+dp[j+1][r][1]);
					}
				}
			}
		}
	}
	int ans=0;
	ffor(i,0,(1<<k)-1) ans=max(ans,dp[1][n][i]);
	cout<<ans;
	return 0;
}

你别说，还挺快的。