dwjshift's Blog

bzoj1495 [NOI2006]网络收费

| Comments

原文发表时间:2014-07-26
这题是今年市选那时候的坑了,现在才来填- -
首先显然要把收费转化成对于单个点的。如果把的路由点也称为A类,的称为B类,观察那个表可以发现,每个路由点实际上收取的就是子树中同类用户的费用。换言之,如果确定了一个用户以及其每个祖先的类型,就可以计算这个叶节点要收取的费用了。
因此,可以先预处理出每个用户和其每个祖先类型相同时要收取的费用,然后就可以dp了。把祖先状压一下,表示第个点子树内有个A类用户,祖先的状态为时最少的费用。可以枚举两个子节点的第二维状态来进行转移。
分析一下时间复杂度。若根节点为第层,则第层共有个点。每个点有个祖先,即祖先有个状态。子树内有个用户,则其子节点的第二维就有个状态。因此转移的总复杂度为

大概就是
但是空间只有64M实在是丧心病狂。观察发现第二、三维的状态数为,所以压到一起存即可。
我太,调了一晚上才A……不过第一次交上去#4,玩了玩常数就跑到#1了,真是感人肺腑。

code

玩过常数的比较难看所以就贴玩常数之前的吧

#include <cstdio>
#include <cctype>
#include <cstring>
#define repu(i,x,y) for (i=x; i<=y; ++i)
#define repd(i,x,y) for (i=x; i>=y; --i)
using namespace std;
    
int n,m,i,j,k,l,w,t,type[2048],c[2048],dep[2048],flow[2048][10],f[2048][2048],ans;
char ch;
    
inline int getint()
{
    while (!isdigit(ch=getchar()));
    int ret=ch-'0';
    while (isdigit(ch=getchar()))
        ret=ret*10+ch-'0';
    return ret;
}
    
inline int lca(int u,int v)
{
    while (u!=v)
        (u>v?u:v)>>=1;
    return u;
}
    
inline void min(int &x,int y)
{
    if (y<x)
        x=y;
}
    
void dp()
{
    repu(i,m,(m<<1)-1)
        repu(j,0,m-1)
        {
            (type[i]?f[i][1<<n|j]:f[i][j])=c[i];
            repu(k,0,n-1)
                (j>>k&1?f[i][j]:f[i][1<<n|j])+=flow[i][k];
        }
    repd(i,m-1,1)
    {
        memset(f[i],80,sizeof(f[i]));
        repu(j,0,1<<n-dep[i]-1)
            repu(k,0,1<<n-dep[i]-1)
                repu(l,0,(1<<dep[i])-1)
                {
                    t=l+((j+k>=1<<n-dep[i]-1)<<dep[i]);
                    min(f[i][j+k<<dep[i]|l],f[i<<1][j<<dep[i]+1|t]+f[i<<1|1][k<<dep[i]+1|t]);
                }
    }
}
    
int main()
{
    m=1<<(n=getint());
    repu(i,m,(m<<1)-1)
        type[i]=getint();
    repu(i,m,(m<<1)-1)
        c[i]=getint();
    repu(i,2,(m<<1)-1)
        dep[i]=dep[i>>1]+1;
    repu(i,m,(m<<1)-2)
        repu(j,i+1,(m<<1)-1)
            t=dep[lca(i,j)],flow[i][t]+=w=getint(),flow[j][t]+=w;
    dp();
    ans=f[1][0];
    repu(i,1,(m<<1)-1)
        min(ans,f[1][i]);
    printf("%d\n",ans);
    return 0;
}

Comments

comments powered by Disqus