题目概述

有一个长度为 $n​$ 的 $01​$ 串，你可以每次将相邻的 $k​$ 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 $k​$ 个字符确定。你需要求出你能获得的最大分数。

解题报告

这是道假题，首先最暴力的方法就是定义 $f[i][j][k][s]$ 表示把 $[i,j]$ 合并为 $s$ ，$s$ 的长度为 $k$ 的最优解。这样的话会炸飞天。接着我们发现分数都是正数，所以肯定能合并就合并，也就是说长度是已知的……根本不用记录长度QAQ。

那么现在的定义就是 $f[i][j][s](k=(j-i)\ mod\ (K-1)+1)$ ，区间DP一下会发现复杂度是 $O(n^3\times 2^7)$ ，还是会炸？这不是搞事情吗？然后我就开始换定义，寻找性质，最后实在不行去翻了题解。

……………………………………………………………………………………………………………………………………………………………………

什么？怎么就是这么写的？？？重新分析了复杂度发现复杂度应该是 $O({n\choose 3}\times 2^7)$ ……是能过的Orz。

示例程序

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=300,maxk=8,maxs=1<<maxk;

int n,K,s[maxn+5],c[maxs],w[maxs];
LL f[maxn+5][maxn+5][maxs>>1],ans;

#define NOW (a<<r|b)
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d",&n,&K);char ch=getchar();while (!isdigit(ch)) ch=getchar();
    for (int i=1;i<=n;i++) s[i]=ch-48,ch=getchar();
    for (int i=0;i<(1<<K);i++) scanf("%d%d",&c[i],&w[i]);
    memset(f,192,sizeof(f));for (int i=1;i<=n;i++) f[i][i][s[i]]=0;
    for (int L=2;L<=n;L++)
        for (int i=1,j=L;j<=n;i++,j++)
            for (int k=i;k<j;k++){
                int l=(k-i)%(K-1)+1,r=(j-k-1)%(K-1)+1,len=(L-1)%(K-1)+1;
                if (l+r>K) continue; //左边和右边长度加起来超过K，说明不能合并，跳过
                for (int a=0;a<(1<<l);a++)
                    for (int b=0;b<(1<<r);b++)
                        if (len==1) f[i][j][c[NOW]]=max(f[i][j][c[NOW]],f[i][k][a]+f[k+1][j][b]+w[NOW]);
                        else f[i][j][NOW]=max(f[i][j][NOW],f[i][k][a]+f[k+1][j][b]);
            }
    for (int k=0;k<(1<<K-1);k++) ans=max(ans,f[1][n][k]);
    return printf("%lld\n",ans),0;
}