记录编号	259883	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2016]字符合并	最终得分	100
用户昵称	Fancy	是否通过	通过
代码语言	C++	运行时间	4.459 s
提交时间	2016-05-11 19:59:39	内存使用	92.58 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
int n,k,m,a[305],c[260],w[260];
long long ans,f[305][305][130],g[260];
int main()
{
	freopen("merge_2016.in","r",stdin);
	freopen("merge_2016.out","w",stdout);
	memset(f,-1,sizeof(f));
	scanf("%d%d",&n,&k);
	m=1<<k;
	for(int i=1,x;i<=n;i++)
		scanf("%1d",&x),f[i][i][x]=0;
	for(int i=0;i<m;i++) scanf("%d%d",&c[i],&w[i]);
	for(int len=1,end=1;len<n;len++,end=(len-1)%(k-1)+1)
		for(int i=1;i+len<=n;i++)
			for(int j=i+end-1;j<i+len;j+=k-1)
				for(int x=0;x<(1<<end);x++)
					if(f[i][j][x]!=-1)
						for(int y=0;y<=1;y++)
							if(f[j+1][i+len][y]!=-1)
							{
								if(end==k-1) f[i][i+len][c[(x<<1)+y]]=std::max(f[i][i+len][c[(x<<1)+y]],f[i][j][x]+f[j+1][i+len][y]+w[(x<<1)+y]);
								else f[i][i+len][(x<<1)+y]=std::max(f[i][i+len][(x<<1)+y],f[i][j][x]+f[j+1][i+len][y]);
							}
	for(int i=0;i<(m>>1);i++) ans=std::max(ans,f[1][n][i]);
	printf("%lld\n",ans);
}