[POJ1155]TELE(树形背包dp)

[POJ1155]TELE(树形背包dp)

看到这道题的第一眼我把题目看成了TLE

这道题是树形背包dp的经典例题

题目描述(大概的):

给你一棵树，每条边有一个cost，每个叶节点有一个earn

要求在earn的和大于等于cost的和的前提下问最多能连接到多少个叶节点

思路:

这道题卡了我0.5month

(因为我太懒了)

核心思路

用dp[x][k]表示x为根的子树里连接到k个叶节点时最大的利润(earn和-cost和)

那么for嵌套顺序应当是

for(int s=cd[x];s;s--/*int d=cd[t];d;d-- <-- It is wrong*/)
            {
                for(int d=min(cd[t],s);d;d--/*int s=cd[x];s>=d;s-- <-- It is wrong*/)
                {
                    if(dp[x][s-d]!=-2147483647){dp[x][s]=max(dp[x][s],dp[x][s-d]+dp[t][d]-e[i].v);}
                }
            }

没错，也就是外层枚举x的体积，内层枚举t的体积，都是从大到小

至于为什么？

因为t的所有可能体积的dp你只能将其中一个装进x的dp里

听说这叫分组背包？反正我看着也差不多

此后就可以开始快乐地dfs了

(为什么看不少人都用滚动数组呢...dp[3001][3001]也不大啊)

剩下还可以加一些小小的优化

看代码吧

#include<cstdio>
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
struct sumireko
{
    int to,ne,v;
}e[3001];
int he[3001],cnt;
void addline(int f,int t,int vin)
{
    e[++cnt].to=t;
    e[cnt].ne=he[f];
    e[cnt].v=vin;
    he[f]=cnt;
    return;
}

//bool v[3001];
//写完才注意到是有向边，所以v意义不大，完全可以全部抛弃
//但删完之后反而变慢了
//越简化越慢也是有毒
int n,m,cd[3001];//其中cd数组与下面的findd()一起使用，用于找出每个节点的子树有几个叶节点，从而省点时间(大概)

int findd(int x)
{
    if(x>(n-m))return cd[x]=1;
    for(int i=he[x];i;i=e[i].ne)
    {
        int t=e[i].to;
        cd[x]+=findd(t);
    }
    return cd[x];
}

int dp[3001][3001];

void dfs(int x)
{
    for(int i=he[x];i;i=e[i].ne)
    {
        int t=e[i].to;
        dfs(t);
        for(int s=cd[x];s;s--/*int d=cd[t];d;d-- <-- It is wrong*/)
        {
            for(int d=min(cd[t],s);d;d--/*int s=cd[x];s>=d;s-- <-- It is wrong*/)
            {
                if(dp[x][s-d]!=-2147483647)dp[x][s]=max(dp[x][s],dp[x][s-d]+dp[t][d]-e[i].v);
            }
        }
    }
    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n-m;i++)
    {
        int k,tin,vin;
        scanf("%d",&k);
        for(int j=1;j<=k;j++)
        {
            scanf("%d%d",&tin,&vin);
            addline(i,tin,vin);
        }
    }
    findd(1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=cd[i];j++)
        {
            dp[i][j]=-2147483647;//初始化
        }
    }
    for(int i=n-m+1;i<=n;i++)
    {
        scanf("%d",&dp[i][1]);
    }
    dfs(1);
    for(int i=cd[1];i>=0;i--)
    {
        if(dp[1][i]>=0)
        {
            printf("%d",i);
            return 0;
        }
    }
    return 0;
}