记录编号	388902	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2269.[HAOI 2016]字符合并	最终得分	100
用户昵称	Bennettz	是否通过	通过
代码语言	C++	运行时间	1.257 s
提交时间	2017-03-30 07:58:21	内存使用	2.28 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#define up(i,j,n) for(int i=j;i<=n;i++)  
#define down(i,j,n) for(int i=j;i>=n;i--)  
#define LL long long
using namespace std;
LL f[305][305][2],g[305][305],ans[305],tmp[305];//f[i][j][0]和f[i][j][1]表示i到j区间合并成0或1的最大分数，g[j][s]表示当前i到j合并成s的最大分数 
int a[305],x,c[305],v[305],n,m;
inline int in(){
	char c=getchar();int ans=0;
	while(!(c>='0'&&c<='9'))c=getchar();
	while(c>='0'&&c<='9')ans=ans*10+c-48,c=getchar();
	return ans;
}
int _521(){
	freopen("merge_2016.in","r",stdin);
	freopen("merge_2016.out","w",stdout);
	n=in();m=in();x=(1<<m);
	up(i,1,n)a[i]=in();
	up(i,0,x-1)c[i]=in(),v[i]=in();
	memset(f,-1,sizeof(f));  
    up(i,1,n) f[i][i][a[i]]=0;
    down(i,n-m+1,1){
    	memset(g,-1,sizeof(g));
    	int now=1;
    	g[i][0]=f[i][i][0];g[i][1]=f[i][i][1];
    	up(j,i+1,n){
    		up(s,0,(1<<now)-1)
    			if(g[j-1][s]>=0)
    				for(int k=j;k<=n;k+=m-1){
    					if(f[j][k][0]>=0)g[k][s<<1]=max(g[k][s<<1],g[j-1][s]+f[j][k][0]);
    					if(f[j][k][1]>=0)g[k][s<<1|1]=max(g[k][s<<1|1],g[j-1][s]+f[j][k][1]);
					}
			if(++now==m){
				memset(tmp,-1,sizeof(tmp));
				up(k,0,(1<<m)-1)
					if(g[j][k]>=0)tmp[c[k]]=max(tmp[c[k]],v[k]+g[j][k]);
                f[i][j][0]=g[j][0]=tmp[0];
                f[i][j][1]=g[j][1]=tmp[1];
                now=1;
			}
		}
	}
	up(i,1,n) for(int j=i;j<=n;j+=m-1) ans[j]=max(ans[j],ans[i-1]+max(f[i][j][0],f[i][j][1]));
	printf("%lld\n",ans[n]);
	
	return 0;
}
int _520=_521();
int main(){;}