BZOJ 4565 [Haoi2016] 字符合并

Description

Input

Output

输出一个整数表示答案

Sample Input

Sample Output

HINT

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

DP+神奇的记录方式~

迷之复杂度……理论上应该是过不了的啊……究竟有多少状态没有搜到啊……

因为从小到大排序刚好是0~(1<<k)-1，所以直接用数组按顺序记录输入的值就好了~

用f[i][j][z]表示区间[i,j]最终消成z（二进制记录状态）的最大得分，那么每次枚举区间mid值（其中mid到j一定是k-1的倍数，否则状态有误），更新即可~

转移方程：f[i][j][z<<1]=max(f[i][j][z<<1],f[i][mid-1][z]+f[mid][j][0]); f[i][j][z<<1|1]=max(f[i][j][z<<1|1],f[i][mid-1][z]+f[mid][j][1]);

注意：

（1）初始化中memset用128更新出来是负无穷，不是正值；

（2）题目中部分数据范围缺失，点开“k<=8”里面有补充，w[i]是10^9，所以f[i][j][z]要开long long；

（3）题目中已有k，不能再用它来做变量（其实只有我自己会出现这样的问题吧--）.

#include<cstdio>#include<cstring>#include<iostream>using namespace std;#define ll long longint n,s[301],c[1<<8],w[1<<8],k;ll f[301][301][1<<8],inf,ans;char ss[301];int read(){	int totnum=0;char ch=getchar();	while(ch<'0' || ch>'9') ch=getchar();	while(ch>='0' && ch<='9') {totnum=(totnum<<1)+(totnum<<3)+ch-'0';ch=getchar();}	return totnum;}int main(){	n=read();k=read();scanf("%s",ss+1);	for(int i=1;i<=n;i++) s[i]=ss[i]-'0';	for(int i=0;i<(1<<k);i++) c[i]=read(),w[i]=read();	memset(f,128,sizeof(f));inf=f[0][0][0];	for(int i=1;i<=n;i++) f[i][i][s[i]]=0;	for(int l=2;l<=n;l++)	  for(int i=1;i+l-1<=n;i++)	  {	  	int j=i+l-1,len=j-i;	  	while(len>k-1) len-=k-1;	  	for(int mid=j;mid>i;mid-=k-1)	  	  for(int z=0;z<(1<<len);z++)	  	    if(f[i][mid-1][z]!=inf)	  	    {	  	    	if(f[mid][j][0]!=inf) f[i][j][z<<1]=max(f[i][j][z<<1],f[i][mid-1][z]+f[mid][j][0]);	  	    	if(f[mid][j][1]!=inf) f[i][j][z<<1|1]=max(f[i][j][z<<1|1],f[i][mid-1][z]+f[mid][j][1]);	  	    }	  	if(len==k-1)	  	{	  		ll g[2];g[0]=g[1]=inf;	  		for(int z=0;z<(1<<k);z++)	  		  if(f[i][j][z]!=inf) g[c[z]]=max(g[c[z]],f[i][j][z]+w[z]);	  		f[i][j][0]=g[0];f[i][j][1]=g[1];	  	}	  }	for(int i=0;i<(1<<k);i++) ans=max(ans,f[1][n][i]);	PRintf("%lld/n",ans);	return 0; }