bzoj4593: [Shoi2015]聚变反应炉

这道题的难点其实是在设DP方程，见过就应该会了

令f0,i表示先激发i的父亲，再激发i，把i的整棵子树都激发的最小费用

f1,i表示先激发i，再激发i的父亲，把i的整棵子树都激发的最小费用

设x,y为i的孩子，先激发x再激发i再激发y有

f0,i=∑(f1,y-cy)+∑f0,x+di-cfa

f1,i=∑(f1,y-cy)+∑f0,x+di

其中差的只有cfa，即0<=f1,i-f0,i<=1，对于typeA就容易做了，若两者相等就选f1，它可以消父亲，否则选f0，因为父亲消的次数有限，而即使消了也只是和选f0得到相同的结果

对于TypeB做树上背包，Fi,j表示第i个点，孩子节点给它贡献了j的最小费用，更新f0,f1

我码力太弱了。。在判断i是否已经被全部消完的时候f0和1要分开判。。。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

using namespace std;

struct node

{

    int x,y,next;

}a[];int len,last[];

void ins(int x,int y)

{

    len++;

    a[len].x=x;a[len].y=y;

    a[len].next=last[x];last[x]=len;

}

int n,d[],c[]; bool type;

int f[][],F[][],li[],t[];

void dfs(int x,int fr)

{

    if(type==false)

    {

        f[][x]=max(d[x]-c[fr],);

        f[][x]=d[x];

    }

    else F[x][]=;

    int sumc=;

    for(int k=last[x];k;k=a[k].next)

    {

        int y=a[k].y;

        if(y!=fr)

        {

            dfs(y,x);sumc+=c[y];

            if(type==false)

            {

                if(f[][y]==f[][y])

                {

                    f[][x]+=f[][y]-c[y]*((d[x]-c[fr])>=c[y]);

                    f[][x]+=f[][y]-c[y]*(d[x]>=c[y]);

                    d[x]-=c[y];

                }

                else

                    f[][x]+=f[][y], f[][x]+=f[][y];

            }

            else

            {

                memset(t,,sizeof(t));

                for(int i=min(sumc,li[x]);i>=;i--)t[i]=F[x][i]+f[][y];

                for(int i=min(sumc,li[x]);i>=;i--)

                {

                    int u=min(sumc,i+c[y]);

                    if(i+c[y]>li[x])t[u]=min(t[u],F[x][i]+f[][y]);

                    else t[u]=min(F[x][u]+f[][y],F[x][i]+f[][y]);

                }

                memcpy(F[x],t,sizeof(F[x]));

                li[x]+=c[y];

            }

        }

    }

    if(type==true)

    {

        for(int i=min(sumc,li[x]);i>=;i--)

        {

            f[][x]=min(f[][x],F[x][i]+max(d[x]-i-c[fr],));

            f[][x]=min(f[][x],F[x][i]+max(d[x]-i,));

        }

    }

}

int main()

{

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&d[i]);

    type=false;

    for(int i=;i<=n;i++)

        scanf("%d",&c[i]),type|=(c[i]>);

    int x,y;

    for(int i=;i<n;i++)

    {

        scanf("%d%d",&x,&y);

        ins(x,y),ins(y,x);

    }

    memset(f,,sizeof(f));

    memset(F,,sizeof(F));

    dfs(,);

    printf("%d\n",f[][]);

    return ;

}

巴特西

bzoj4593: [Shoi2015]聚变反应炉

最新文章

热门文章