记录编号	394585	评测结果	AAAAAAAAWWAAAAAAAAAA
题目名称	[HAOI 2016]字符合并	最终得分	90
用户昵称	Bennettz	是否通过	未通过
代码语言	C++	运行时间	0.629 s
提交时间	2017-04-13 17:23:03	内存使用	1.45 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
int in(){
	char c=getchar();
	int ans=0;
	while(c>'9'||c<'0')c=getchar();
	while(c<='9'&&c>='0')ans=ans*10+c-48,c=getchar();
	return ans;
}
LL f[305][305][2],g[305][305],ans[305];//f[i][j][0]和f[i][j][1]表示i到j区间合并成0或1的最大分数，g[j][s]表示当前i到j合并成s的最大分数 
int a[305],c[305],v[305];
int orzxtt(){
	freopen("merge_2016.in","r",stdin);
	freopen("merge_2016.out","w",stdout);
	int n=in(),k=in();
	memset(f,-1,sizeof(f));
	for(int i=0;i<n;i++)a[i]=in(),f[i][i][a[i]]=0;
	for(int i=0;i<(1<<k);i++)c[i]=in(),v[i]=in();
	LL max1=0;
	for(int i=n-k;i>=0;i--){//起点 
		memset(g,-1,sizeof(g));
		g[i][0]=f[i][i][0];
		g[i][1]=f[i][i][1];
		int l=1;//操作区间长度-1%k
		for(int j=i+1;j<n;j++){//结束点 
			for(int s=0;s<(1<<l);s++){
				if(g[j-1][s]>=0){//可合并成s; 
					for(int w=j;w<n;w+=k-1){//更新的g的结束点
						if(f[j][w][1]>=0)g[w][s<<1|1]=max(g[w][s<<1|1],g[j-1][s]+f[j][w][1]);//j-w可合并成1,i-j可合并成s,i-w可合并成s<<1|1 
						if(f[j][w][0]>=0)g[w][s<<1]=max(g[w][s<<1],g[j-1][s]+f[j][w][0]);//j-w可合并成0,i-j可合并成s,i-w可合并成s<<1 
					}
				}
			}
			if(++l==k){
				l=1;
				for(int w=0;w<(1<<k);w++){
					if(g[j][w]>=0)f[i][j][c[w]]=max(f[i][j][c[w]],g[j][w]+v[w]);
					max1=max(max1,f[i][j][c[w]]);
				}
				g[j][0]=f[i][j][0];
				g[j][1]=f[i][j][1];
			}
		}
	}
	//for(int i=0;i<n;i++)for(int j=i;j<n;j+=k-1) ans[j]=max(ans[j],ans[i-1]+max(f[i][j][0],f[i][j][1]));
	printf("%lld\n",max1);
	return 0;
}
int nrottt=orzxtt();
int main(){
	return 0;
}