题外话

这题…. 真 jay 形！

简述题意

由于 codevs 和 bzoj 上的题意都不完整，在此简述题意（~~然而再怎么简述这个题意都很长啊~~ )。
一棵满二叉树的叶子节点是用户，网络公司很 jay 形，要求捆绑收费，对于每一对用户 i,j，要收的费用是 w[i][j]×k，w[i][j] 会在输入数据里给出，而 k 的定义是：
找到 i 和 j 的最近公共祖先 p，以 p 为根的子树里选择 A 收费方式的用户数为 $n_a$, 选择 B 收费方式的用户数为 $n_b$。假如 $n_a$小于 $n_b$, 那么 1A1B 的话 k=1, 全 B 为 2，全 A 为 0。否则 1A1B 对应 K=1, 全 B 为 0，全 A 为 2
所有用户已经选了收费方式，如果要修改就要交钱。第 i 个用户的修改费用为 c[i]（~~居然还区别对待有没有天理有没有人性！~~ )，求修改一些人后交的费用最少值。

题目分析

对于一棵以 k 为根的子树，假如 $n_a$<$n_b$，这个点就标记为 B 点，否则这个点就标记为 A 点，那么对于一个点 i, 假设它是 A，它的一个祖先 j 是 A，那么这个节点就需要交所有和它的祖先是 j 的所有节点 k 的 w[i][k] 的总和的钱，这个总和可以预处理出来。
那么我们可以这样，用 $f(x,num,zt)$表示以 x 节点为根的子树上，有 num 个 A 节点，其所有祖先的状态用状压表示为 zt 的最少交的钱数，对于叶子节点，我们可以根据 zt 来特殊考虑 $f(x,num,zt)$的值，其他的状态转移方程为：
$$f(x,num,zt)=min(f(left,i,zt+s)+f(right,num-i,zt+s));$$
s 表示当前 x 节点的状态是 A 还是 B
然而这样空间无法承受，我们可以再压一维，就是用一种神奇的方式把后面两维的状态合并，具体看代码。

代码

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,m,ans=INT_MAX;
int w[1100][1100],c[1100],fa[1100][1100],co[1100][1100];
int ty[1100];
struct node{int lim,s[2200];}f[2200];
int find(int x,int num,int zt){
    int i,j,ha=0,hb=0;
    for(i=1;i<=n;i++){
        if(zt&1)ha+=co[x][i];
        else hb+=co[x][i];//a:0,b:1
        zt>>=1;
    }
    if(ty[x]==num){ha+=c[x];hb+=c[x];}
    if(num)return ha;//这个点是 A
    else return hb;
}
int dp(int x,int num,int zt,int h){
    //x 号节点，num 个 A 节点，zt 是所有祖先的状态，h 用来确定管辖的子节点数
    int i,j,k,tzt,re,is,hav,xj;//hav: 管辖叶子节点数
    re=f[x].s[f[x].lim*num+zt];//神奇的合并两维的方式
    if(re)return re;
    if(h){
        hav=1<<h;re=INT_MAX;
        if(num<hav-num)is=1;  else is=0;
        if(hav/2<num)xj=num-hav/2;  else xj=0;
        tzt=(zt<<1)|is;
        for(i=xj;i<=hav/2&&i<=num;i++)
            re=min(re,dp(x<<1,i,tzt,h-1)+dp((x<<1)|1,num-i,tzt,h-1));
    }
    else re=find(x-m+1,num,zt);//叶子节点特判
    f[x].s[f[x].lim*num+zt]=re;
    return re;
}
int main()
{
    int i,j,k,x,y;
    n=read();m=1<<n;
    for(i=1;i<=m;i++)ty[i]=read();
    for(i=1;i<=m;i++)c[i]=read();
    for(i=1;i<=m;i++)
        for(j=i+1;j<=m;j++)w[j][i]=w[i][j]=read();
    for(i=1;i<=m;i++)//找到叶子节点的每一个祖先
    {   k=i+m-1;for(j=1;j<=n;j++){k=k>>1;fa[i][j]=k;} }
    for(i=1;i<=n+1;i++){//对于每一层的节点的二进制位置的那个 1 的地方
        x=1<<(i-1);y=(1<<i)-1;//每一层节点编号
        for(j=x;j<=y;j++)f[j].lim=x;
    }
    for(i=1;i<=m;i++)//史上最暴力 lca
        for(j=i+1;j<=m;j++)
        for(k=1;k<=n;k++)
        if(fa[i][k]==fa[j][k])
        {co[i][k]+=w[i][j];co[j][k]+=w[i][j];break;}
    for(i=0;i<=m;i++)ans=min(ans,dp(1,i,0,n));
    printf("%d",ans);
    return 0;
}