记录编号	367176	评测结果	AAAAAAAAAA
题目名称	[NOI 2006]网络收费	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.383 s
提交时间	2017-01-28 21:50:49	内存使用	64.46 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2050;
int n,h,tp[N],c[N],f[N][N],sum[N][N];//sum[i][j]表示i和子树j中的点的流量和 
int dp[N][N*2],X[N*2],Y[N*2];//dp[i][j][k]表示深度为i,节点j,祖先类型和B点数为k的最小代价 
//定义，若子树x上nA<nB，则x为A型点(0)，否则为B型点(1) 
#define lc x<<1
#define rc x<<1|1
void getsum(int x,int l,int r){//O(n^2)
	if (l==r){
		for (int i=0;i<n;i++) sum[i][x]=f[i][l];
		return;
	}
	int mid=(l+r)>>1;
	getsum(lc,l,mid);
	getsum(rc,mid+1,r);
	for (int i=0;i<n;i++) sum[i][x]=sum[i][lc]+sum[i][rc];
}
void solve(int x,int H,int l,int r){//O(n^2*logn)
	if (l==r){
		for (int i=0;i<(1<<H);i++){//枚举祖先节点的类型 
			if (tp[l]) dp[x][i<<1]=c[l];
				else dp[x][i<<1|1]=c[l];
			for (int j=0,y=x;j<H;j++,y>>=1){
				if (i>>j&1) dp[x][i<<1|1]+=sum[l][y^1];
					else dp[x][i<<1]+=sum[l][y^1];
			}
		}
		return;
	}
	int mid=(l+r)>>1,s=r-mid,ls=h+1-H;//出了祖先节点类型,剩下ls位 
	solve(lc,H+1,l,mid);
	solve(rc,H+1,mid+1,r);
	for (int i=0;i<(1<<H);i++){//枚举祖先类型(不含自己)
		int tp=i<<ls,tpx=tp,tpy=1<<(ls-1)|tpx;
		//X为x是A型点时的情况,Y为x是B型点时的情况 
		for (int j=0;j<=r-l+1;j++) X[tp|j]=Y[tp|j]=1e9;
		for (int a=0;a<=s;a++)//从左子树取a个 
		for (int b=0;b<=s;b++)//从右子树取b个 
			X[tp|(a+b)]=min(X[tp|(a+b)],dp[lc][tpx|a]+dp[rc][tpx|b]),
			Y[tp|(a+b)]=min(Y[tp|(a+b)],dp[lc][tpy|a]+dp[rc][tpy|b]);
		for (int j=0;j<=r-l+1;j++)
			dp[x][tp|j]=j>s?X[tp|j]:Y[tp|j];
	}
	/*printf("point %d [%d,%d]\n",x,l,r);
	for (int i=0;i<(1<<H);i++){
		printf("\ttype=%d\n\t",i);
		for (int j=0;j<=r-l+1;j++) printf("%d ",dp[x][i<<ls|j]);
		puts("");
	}*/
}
int main()
{
	freopen("networkcost.in","r",stdin);
	freopen("networkcost.out","w",stdout); 
	scanf("%d",&h);n=1<<h;
	for (int i=0;i<n;i++) scanf("%d",&tp[i]);
	for (int i=0;i<n;i++) scanf("%d",&c[i]);
	for (int i=0;i<n;i++)
		for (int j=1;j<n-i;j++)
			scanf("%d",&f[i][i+j]),f[i+j][i]=f[i][i+j];
	getsum(1,0,n-1);
	solve(1,0,0,n-1);
	int ans=1e9;
	for (int i=0;i<=n;i++) ans=min(ans,dp[1][i]);
	printf("%d\n",ans);
	return 0;
}