树形dp基础：选课
链接：登录—专业IT笔试面试备考平台_牛客网
树形dp学得有些糊涂，来写几篇博客捋捋思路。
首先能发现不同的科目之间存在依赖关系，所以建树。然后题目说是没有先修课的科目会以0为根，那么就建一颗以0为根的树，向下延申。
考虑dp，首先是数组的意义，不难想到用dp【i】【j】来表示以i为根，选j门课能获得的最大学分。但是这里因为我们是以0作为根的，所以最后肯定是要输出dp【0】【m】，但是0它不是一门课，所以m此时其实是加了一个1（就是m++），因为0肯定是会被选上的。或者我们就干脆直接让全体都-1，那么dp【0】【m】中的m就还是一开始的m，那么初始化时就应该是让dp【i】【0】=num【i】（num表示学分）。
内部进行dfs时，关键其实是在做一个背包。
void dfs(ll x,ll pre) {dp[x][0]=num[x];for(int i:mas[x]){if(i==pre) continue;dfs(i,x);for(int j=m;j;--j){for(int k=0;k第二维存放的就是一维背包的东西
#include
using namespace std;
#define ll long long
ll n,m,a,b;
vector mas[310];
ll dp[310][310]; //以i为根选j门课程的最大学分
ll num[310];
void dfs(ll x,ll pre)
{dp[x][0]=num[x];for(int i:mas[x]){if(i==pre) continue;dfs(i,x);for(int j=m;j;--j){for(int k=0;k>n>>m;for(int i=1;i<=n;++i){cin>>a>>b;mas[a].push_back(i);num[i]=b;}num[0]=0;dfs(0,-1);cout< 这样就好了，比较水。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！