Description
有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字
符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。
Input
第一行两个整数n，k。接下来一行长度为n的01串，表示初始串。接下来2k行，每行一个字符ci和一个整数wi，ci
表示长度为k的01串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符,wi表示对应的第i种方案对应
获得的分数。1<=n<=300,0<=ci<=1,wi>=1,k<=8
Output
输出一个整数表示答案
Sample Input
3 2
101
1 10
1 10
0 20
1 30
Sample Output
40
【题解】
发现k很小，可以考虑状压。
定义f[i][j][s]表示原串第i到j个字符合成成状态s所获得最大的分数。
初值：
f[i][i][kai[i]]=0;其他=-inf。
转移：
考虑到一段数肯定合得越多越优，所以一段中肯定合得不能再合，剩下的数的个数就是hu=（len-1）%(k-1)。
所以枚举这一段的状态为0---(1<<hu)-1。
考虑到一段数肯定是从左边一个区间一个s1和右边一个区间s2合并而得，所以可以令右边的区间只剩下一个数，又是一个舒服的优化。
如果hu==0即剩下了k个数，则可以枚举每一个状态，f[i][j][c[s]]=f[i][j][s]+w[s]。
代码如下：
#include<bits/stdc++.h> #define int long long using namespace std; const int N=305; int n,k,kai[N],c[N],w[N],f[N][N][N]; inline int read() { char c=getchar(); int x=0,f=1; while(!isdigit(c)) {if(c==‘-‘) f=-1;c=getchar();} while(isdigit(c)) {x=(x<<3)+(x<<1)+c-‘0‘;c=getchar();} return x*f; } signed main() { n=read();k=read(); for(int i=1;i<=n;i++) kai[i]=read(); for(int i=0;i<(1<<k);i++) c[i]=read(),w[i]=read(); for(int i=1;i<=n;i++) { for(int l=0;l<(1<<k);l++) f[i][i][l]=-0x3f3f3f3f; f[i][i][kai[i]]=0; } for(int i=2;i<=n;i++) { for(int j=1;j+i-1<=n;j++) { int y=j+i-1; for(int l=0;l<(1<<k);l++) f[j][y][l]=-0x3f3f3f3f; int she=(i-1)%(k-1); if(!she) she=k-1; for(int l=y;l>j;l-=(k-1)) { for(int s=0;s<1<<she;s++) f[j][y][s<<1]=max(f[j][y][s<<1],f[j][l-1][s]+f[l][y][0]), f[j][y][s<<1|1]=max(f[j][y][s<<1|1],f[j][l-1][s]+f[l][y][1]); } if(she==k-1) { int hu[2];hu[0]=hu[1]=-0x3f3f3f3f; for(int s=0;s<(1<<k);s++) hu[c[s]]=max(hu[c[s]],f[j][y][s]+w[s]); f[j][y][0]=hu[0];f[j][y][1]=hu[1]; } } } int ans=-0x3f3f3f3f; for(int i=0;i<1<<k;i++) ans=max(ans,f[1][n][i]); cout<<ans; }
原文：https://www.cnblogs.com/betablewaloot/p/12194039.html
