题外话

这题….真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;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *