bzoj-4565-区间dp+状压

4565: [Haoi2016]字符合并

Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 542 Solved: 253
[Submit][Status][Discuss]

Description

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

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

Input

第一行两个整数n，k。接下来一行长度为n的01串，表示初始串。接下来2^k行，每行一个字符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
//第3行到第6行表示长度为2的4种01串合并方案。00->1,得10分，01->1得10分，10->0得20分，11->1得30分。

HINT

Source

　　　　　　有很多细节，递推方程想出来了但最后还是看了题解才知道具体的操作。f[i][j][S]表示区间[i,j]合并成状态S获得的最大价值，一开始有一点想不通，比如'1','01','001'用二进制表示都是1，我们怎么识别的，有一个重要的性质是一个长度为k的区间完全合并后的长度就是x=n%(k-1)?n%(k-1):k-1。知道了这点就很nice了。显然一个区间肯定要完全合并才能使得价值最大。对于一个区间，考虑枚举分割点，我们可以枚举合并后最右侧的那一个数来分割这个区间，换句话说就是把[i,j]=[i,m-1]+[m,j] , [m,j]完全合并后得到一个元素，这个m可以不断-(k-1)枚举得到，由于右侧的区间大小不断的+(k-1),相当于左边的区间大小不断地-(k-1),所以这两个子区间完全合并后的元素个数s1,s2是一定的且s2==1。最后一个数可能是0/1，

得到方程 f[i][j][S<<1]=max(f[i][j][S<<1],f[i][m-1][S]+f[m][j][0])

　　　　 f[i][j][S<<1|1]=max(f[i][j][S<<1|1],f[i][m-1][S]+f[m][j][1]) //注意这些状态必须合法才可转移

要注意s1的范围是[1,k-1],当s1=k-1时s1+s2=k,此时还可以再进行合并为一个元素，需要计算一下f[i][j][0/1]。

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define INF 0x3f3f3f3f

 LL f[][][(<<)+];

 char s[];

 int b[(<<)+];

 LL c[(<<)+];

 int main(){

     int n,m,k,i,j;

     scanf("%d%d",&n,&k);

     scanf("%s",s+);

     for(i=;i<(<<k);++i)

         scanf("%d%lld",b+i,c+i);

     memset(f,-INF,sizeof(f));

     LL inf=f[][][];

     for(i=;i<=n;++i) f[i][i][s[i]-'']=;

     for(int len=;len<=n;++len){

         for(i=;i+len-<=n;++i){

             j=i+len-;

             int l=(j-i)%(k-);

             if(!l) l=k-;

             for(int las=j;las>=i;las-=k-){

                 for(int S=;S<(<<l);++S){

                     if(f[i][las-][S]==inf) continue;

                     if(f[las][j][]!=inf)

                     f[i][j][S<<]=max(f[i][j][S<<],f[i][las-][S]+f[las][j][]);

                     if(f[las][j][]!=inf);

                     f[i][j][S<<|]=max(f[i][j][S<<|],f[i][las-][S]+f[las][j][]);

                 }

             }

             if(l==k-){

                 LL g[]={inf,inf};

                 for(int S=;S<(<<k);++S){

                     if(f[i][j][S]!=inf){

                         g[b[S]]=max(g[b[S]],f[i][j][S]+c[S]);

                     }

                 }

                 f[i][j][]=g[];

                 f[i][j][]=g[];

             }

         }

     }

     LL ans=;

     int l=n%(k-)?n%(k-):k-;

     for(i=;i<(<<l);++i)

         ans=max(ans,f[][n][i]);

     cout<<ans<<endl;

     return ;

 }

巴特西