看到这道题的第一眼我把题目看成了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*/)
{
){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[];
],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意义不大，完全可以全部抛弃
//但删完之后反而变慢了
//越简化越慢也是有毒
];//其中cd数组与下面的findd()一起使用，用于找出每个节点的子树有几个叶节点，从而省点时间(大概)
int findd(int x)
{
;
for(int i=he[x];i;i=e[i].ne)
{
int t=e[i].to;
cd[x]+=findd(t);
}
return cd[x];
}
][];
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*/)
{
)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);
;i<=n-m;i++)
{
int k,tin,vin;
scanf("%d",&k);
;j<=k;j++)
{
scanf("%d%d",&tin,&vin);
addline(i,tin,vin);
}
}
findd();
;i<=n;i++)
{
;j<=cd[i];j++)
{
dp[i][j]=-;//初始化
}
}
;i<=n;i++)
{
scanf(]);
}
dfs();
];i>=;i--)
{
][i]>=)
{
printf("%d",i);
;
}
}
;
}