Sunshine’s string(merge.cpp)

【问题描述】

无聊的Sunshine大爷开始研究字符串。他找来了一个长度为n的01字符串，并制定了一些规则：每次可以将k个字符合并，得到一个新的字符并获得一定的分数。追求完美的宇宙金牌爷想知道他最多能获得多少分数。

【输入格式】

第一行两个整数n和k，分别表示字符串的长度和每次合并的长度。

第二行n个0或1的字符。

接下来2^k行，第i行表示长度为k的01串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符和对应的第i种方案对应获得的分数。

【输出格式】

一个整数表示能获得的最大分数。

【样例输入】

3 2

1 0 1

1 10

1 10

0 20

1 30

【样例输出】

40

【数据规模及约定】

————————————————————————————————————————————

【题解】【状压dp】

【发现k比较小，考虑状压

记f[i][j][S]表示把i~j这一段消除成S这个状态能获得的最大分数，转移的时候只考虑将右边的一段消到只有一个字符，然后加到左边去。并且f[i][j][S]可以直接转移到f[i][j][c[S]]。

复杂度O(n^3*2^k)

看起来复杂度很高但是可以发现转移其实很少】

#include
    
     #include
     
      #include
      
       #define ll long long using namespace std;ll f[310][310][1<<8];int c[1<<8],w[1<<8],a[310],n,k;int main(){	freopen("merge.in","r",stdin);	freopen("merge.out","w",stdout);	int i,j;	scanf("%d%d",&n,&k);	for(i=1;i<=n;++i) scanf("%d",&a[i]);	for(i=0;i<(1<
       
        =k) len-=k-1;	  	for(int l=j;l>i;l-=k-1)	  	 for(int h=(1<