【洛谷P2014】选课【树形DP】【背包】

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P2014
有$n$门功课，一些功课有先修课。每门功课都有学分。求选出$m$门功课能获得的最大学分。

思路：

树形DP+背包。
很明显，这道题肯定是设$f[u][j]$表示以$u$为根的子树选出$j$门课程学习能获得的最大学分。
那么对于$u$的任意一棵子树$v$，我们设它有$s$个结点，那么我们就可以在这棵子树中选择任意$k\in [0\sim s]$个结点来转移。
那么方程很明显就是
$$f[u][j]=max(f[u][j],f[u][j-k-1]+f[v][k])$$
为什么$j-k$之后还要减$1$呢？
因为要选择$u$的子树，那么$u$是肯定得选的，所以在转移的时候可以忽略掉这一个结点。
那么很明显，最终答案就是$f[0][m]$。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 400
using namespace std;
int n,m,f[N][N],head[N],tot;
struct edge
{
int next,to,s;
}e[N];
void add(int from,int to,int s)
{
e[++tot].to=to;
e[tot].s=s;
e[tot].next=head[from];
head[from]=tot;
}
int dp(int x)
{
int sum=1;
//以x为跟的节点个数
for (int i=head[x];~i;i=e[i].next)
{
int sonsum=dp(e[i].to);
//子树节点个数
sum=sum+sonsum;
for (int j=sum-1;j>=0;j--)
//背包，要降序
for (int k=0;k<sonsum;k++)
if (j-k>=1)
f[x][j]=max(f[x][j],f[x][j-k-1]+f[e[i].to][k]);
}
return sum;
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
int x,y;
for (int i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
f[i][0]=y;
add(x,i,y);
}
dp(0);
printf("%dn",f[0][m]);
return 0;
}

最后

以上就是淡然小猫咪为你收集整理的【洛谷P2014】选课【树形DP】【背包】的全部内容，希望文章能够帮你解决【洛谷P2014】选课【树形DP】【背包】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。