问题 A: [Haoi2016]字符合并

时间限制: 2 Sec 内存限制: 256 MB

提交: 73 解决: 35

[提交][状态][讨论版]

题目描述

有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字

符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。

输入

第一行两个整数n，k。接下来一行长度为n的01串，表示初始串。接下来2k行，每行一个字符ci和一个整数wi，ci

表示长度为k的01串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符,wi表示对应的第i种方案对应

获得的分数。1<=n<=300,0<=ci<=1,wi>=1,k<=8

输出

输出一个整数表示答案

样例输入

3 2

101

1 10

1 10

0 20

1 30

样例输出

40

//第3行到第6行表示长度为2的4种01串合并方案。00->1,得10分，01->1得10分，10->0得20分，11->1得30分。

因为最多只有8位，可以考虑状压。f[i][j][k]表示区间i~j缩到只剩下k状态时，最大和。

那么就得考虑怎么转移了。首先要枚举每个区间这没问题，不可能剩余>k位，而每次合并都会减少k-1位，所以在当前枚举的区间，确定能缩的全部缩完后，还剩下多少个点，记为len。那么最多会有1<

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long longusing namespace std;int read(){    int sum=0,f=1;char x=getchar();    while(x<'0'||x>'9'){
    if(x=='-')f=-1;x=getchar();}    while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}    return sum*f;}int n,m,b[(1<<8)+2];ll f[305][305][(1<<8)+2],v[(1<<8)+2];char s[305];int yjn(){    freopen("merge.in","r",stdin);    freopen("merge.out","w",stdout);    memset(f,-1,sizeof(f));    n=read();m=read();    scanf("%s",s+1);    for(int i=1;i<=n;i++)f[i][i][s[i]-'0']=0;    for(int i=0;i<(1<
          
           m)len-=m-1; for(int k=j;k>=i;k-=m-1) for(int S=0;S<(1<