[JSOI2008]魔兽地图DotR

题意

题目链接

给一棵树，选取叶节点一次需要花费\(w_i\)代价，获得\(v_i\)收益，一个叶子节点最多选择\(l_i\)次，非叶子节点也有收益\(v_i\)，它由其叶子节点按照一定比例混合得来。问花费为\(m\)所能获得的最大收益

思路

神仙树形dp

首先看出来是树形dp，之后就一定是树上背包啦~~~

设\(f[i][j][k]\)表示在\(i\)号节点，向父亲传\(j\)次，且\(i\)子树共花费了\(k\)代价的最大收益

先枚举当前节点的选取次数\(l\)

用\(g[i][j]\)表示考虑了当前子树的前\(i\)个儿子，且它们总花费代价为\(j\)的最大收益，转移方程为\(g[i][j]=max(g[i-1][j-k]+f[v][l*e][k])\)，得到\(g[tot][j]\)（即所有儿子，其中e为v儿子转换成父亲的比例）

再枚举当前节点向父亲传的次数\(j\)

有\(f[rt][j][k]=max(g[tot][k]+v[rt]*(l-j))\)

另外，由于可能不止一棵树，需要用背包对森林进行合并，这个操作和01背包相同

Code

#include<bits/stdc++.h>
#define N 55
#define M 2005 
#define Max(x,y) ((x)>(y) ? (x):(y))
using namespace std;
int n,m;
int S[N],W[N],L[N];//力量，价格，数量 
int rd[N];
int f[N][105][M];//在i节点选择j个上传，子树花费k代价的总力量值 
int ans[M],g[N][M],tot;

struct Edge
{
    int next,to,val;//val是使用次数 
}edge[N*N];int head[N],cnt;
void add_edge(int from,int to,int val)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].val=val;
    head[from]=cnt; 
}

template <class T>
void read(T &x)
{
    char c;int sign=1;
    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
void dfs(int rt)//处理rt子树 
{
    if(!head[rt])//叶子 
    {
        L[rt]=min(L[rt],m/W[rt]);
        for(int i=0;i<=L[rt];++i)
            for(int j=0;j<=i;++j)
                f[rt][j][i*W[rt]]=(i-j)*S[rt];
        return;
    }
    L[rt]=100000000;
    for(int i=head[rt];i;i=edge[i].next)
    {
        int v=edge[i].to;
        dfs(v);
        L[rt]=min(L[rt],L[v]/edge[i].val);//判边界 
        W[rt]+=W[v]*edge[i].val;
    }
    L[rt]=min(L[rt],m/W[rt]);//神装限制数量 
    memset(g,-50,sizeof(g));
    g[0][0]=0;
    for(int l=L[rt];l>=0;--l)
    {
        tot=0;
        for(int i=head[rt];i;i=edge[i].next)
        {
            int v=edge[i].to;
            ++tot;
            for(int j=0;j<=m;++j)//前tot个儿子共花费j 
            for(int k=0;k<=j;++k)//前tot-1个花费k 
            {
                g[tot][j]=Max(g[tot][j],g[tot-1][k]+f[v][l*edge[i].val][j-k]);
            }   
        }
        for(int j=0;j<=l;++j)//上传j个
            for(int k=0;k<=m;++k)
                f[rt][j][k]=Max(f[rt][j][k],g[tot][k]+S[rt]*(l-j));
    }
}
int main()
{
    memset(f,-50,sizeof(f));
    read(n);read(m);
    for(int i=1;i<=n;++i)
    {
        char op[2];
        read(S[i]);
        scanf("%s",op);
        if(op[0]=='A')//神装 
        {
            int c; read(c);
            for(int j=1;j<=c;++j)
            {
                int x; read(x);
                int p; read(p);
                add_edge(i,x,p);
                ++rd[x];
            }
        }
        else read(W[i]),read(L[i]);
    }
    for(int i=1;i<=n;++i)
    {
        if(!rd[i]) 
        {
            dfs(i);
            for(int k=m;k>=0;--k)
                for(int j=0;j<=k;++j)
                    ans[k]=Max(ans[k],ans[k-j]+f[i][0][j]);
        }
    }
    cout<<ans[m]<<endl;
    return 0;
}

[JSOI2008]魔兽地图DotR

原文：https://www.cnblogs.com/Chtholly/p/11431819.html