HAOI2010 软件安装有依赖的背包DP

布满荆棘的人生 2021-11-23 14:58 247阅读 0赞

#### 题目描述 ####

现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一 些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大(即Vi的和最大)。

但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件i依赖软件j)。幸运的 是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。

我们现在知道了软件之间的依赖关系：软件i依赖软件Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一 次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。

#### 输入格式 ####

第1行：N，M (0<=N<=100．0<=M<=500)

第2行：W1，W2，…，Wi，…，Wn(0<=Wi<=M)

第3行：V1，V2，…，Vi，…，Vn(0<=Vi<=1000)

第4行：D1，D2，…，Di，…，Dn(0<=Di<=N，Di≠i)

#### 输出格式 ####

一个整数，代表最大价值。

#### 样例 ####

#### 样例输入 ####

3 10
    5 5 6
    2 3 4
    0 1 1

#### 样例输出 ####

用这个题呢，首先来复习一下背包DP，f\[i\]\[v\]=max(f\[i\]\[v\],f\[i-1\]\[v-c\[i\]\]+w\[i\]) 然后发现只从i-1到i转移，直接搞掉第一维，然后调整循环顺序，采用v到0的倒序保证只取一次，然后强一点的背包是完全和多重，完全可以把循环顺序反过来，保证随意取，而多重可以用二进制优化，当然单队也是可以的，这里不再赘述，具体可以参见DD大牛的背包九讲（看了很多遍），那么在简单的分组DP中，保证一个组只取一个或者不去，我们的转移应该这样写;

for  每一组

for v...0

for 每一个元素

f\[i\]\[v\]=max(f\[i\]\[v\],f\[i-1\]\[v-c\[i\]\]+w\[i\];

至于循环顺序，必须将枚举体积套在枚举每一元素的外面，如果放里面其实就和没有组别一样了，不能保证每组只能取一个。

有依赖的DP就和分组DP很像，我们可以把没有依赖的物品称主件，有依赖的称为附件，本题是在树上，那么一定要定义给以i为根的子树分配V的空间所能达到的最大价值，那然后发现多个儿子转移到父亲似乎不好转移，父亲好像要给儿子分配时间。

重新考虑一下，对于一个主件对应的几个附件可以看作是决策集合，那么这个集合在子树中有指数级多的的决策，怎么办呢？如果我们优化的话，对于每一个决策，我们要找相同体积找价值最大的，这是显然的，然后从子树转移过来的时候，我们会发现所谓的f\[i\]\[v\]就是V体积下对应的那个最大的价值，决策已经保证最优，只要循环V转移即可，道理同上。

别的扯完了，我们可以看一看这个题目，每个物品只有一个出边，仍然可能是基环森林。。。。那么可以通过分析得到，这题取软件不分先后顺序，只要我的依赖取上就行，哪怕是在我后边取，那么一个环共生共灭，然后就可以缩点了，缩点真麻烦，缩完真简便。。。只要在缩完点的森林中建一个虚根0，价值和体积都为0,然后就成了0为根的一棵树，然后这个题就被我们一步一步肢解了。。

最后说一句，如何保证父亲不取的时候子树均不能做贡献。

（只要在第二层循环体积的时候只循环到v\[x\]，别的不更新即可。）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<vector>
    #include<algorithm>
    using namespace std;
    const int N=150,V=550;
    vector<int> q[N];
    int fr[N],ft[N],s[N],w[N],v[N],size[N],stack[N],du[N],c[N],low[N],vi[N],wi[N],dfn[N],rt=-1,num,cnt,kt,top,n,m,tt,tp,f[N][V];
    bool ins[N],b[N];
    struct node{
         int fr,to,pr;}mo[N],no[N];
    struct qe{
         int a,b;};
    int rd()
    {
        char cc=getchar();
        int s=0,w=1;
        while(cc<'0'||cc>'9') {
         if(cc=='-') w=-1;cc=getchar();}
        while(cc>='0'&&cc<='9') s=(s<<3)+(s<<1)+cc-'0',cc=getchar();
        return s*w;
    }
    void init(int x,int y)
    {
        no[++tp].fr=x;
        no[tp].to=y;
        no[tp].pr=ft[x];
        ft[x]=tp;du[y]++;
    }
    void add(int x,int y)
    {
        mo[++tt].fr=x;
        mo[tt].to=y;
        mo[tt].pr=fr[x];
        fr[x]=tt;
    }
    void tarjan(int x)
    {
        low[x]=dfn[x]=++num;
        stack[++top]=x;ins[x]=1;
        for(int i=fr[x];i;i=mo[i].pr)
        {
            int y=mo[i].to;
            if(!dfn[y])
            {
                tarjan(y);
                low[x]=min(low[x],low[y]);
            }
            else if(ins[y]) low[x]=min(low[x],dfn[y]);
        }
        if(low[x]==dfn[x])
        {
            int y,s=0;++cnt;
            do{
                y=stack[top--];
                vi[cnt]+=v[y];
                wi[cnt]+=w[y];
                c[y]=cnt;
                ins[y]=0;
            }while(x!=y);
        }
    }
    void rebuild()
    {
        for(int x=1;x<=n;x++) 
            for(int i=fr[x];i;i=mo[i].pr)
            {
                int to=mo[i].to;
                if(c[x]!=c[to]) init(c[x],c[to]);
            }
        for(int i=1;i<=cnt;i++)
            if(!du[i]) init(0,i);
    }
    void dp(int x)
    {
        for(int i=m;i>=vi[x];i--) f[x][i]=max(f[x][i],f[x][i-vi[x]]+wi[x]);
        for(int i=ft[x];i;i=no[i].pr)
        {
            int to=no[i].to;
            dp(to);
            for(int i=m;i>=vi[x];i--)
                for(int j=0;j<=i-vi[x];j++)
                f[x][i]=max(f[x][i],f[x][i-j]+f[to][j]);
        }
    }
    int main()
    {
        n=rd();m=rd();
        int x,y,mn=-0x7fffffff;
        for(int i=1;i<=n;i++) v[i]=rd();
        for(int i=1;i<=n;i++) w[i]=rd();
        for(int i=1;i<=n;i++)
        {
            x=rd();
            if(x!=0) add(x,i);
        }
        for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
        rebuild();
        dp(0);
        printf("%d\n",f[0][m]);
    }
    /*
    g++ 1.cpp -o 1
    ./1
    4 15
    3 2 5 5
    3 2 10 7
    3 1 2 1
    */

转载于:https://www.cnblogs.com/starsing/p/11179296.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211122/31b7ba09c98e41ad9799b643b81f1499.png