AcWing 286. 选课（有依赖的树形dp / dfs序优化）

本文主要是介绍AcWing 286. 选课（有依赖的树形dp / dfs序优化），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

学校实行学分制。

每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。

学校开设了 N 门的选修课程，每个学生可选课程的数量 M 是给定的。

学生选修了这 M 门课并考核通过就能获得相应的学分。

在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其他的一些课程的基础上才能选修。

例如《Windows程序设计》必须在选修了《Windows操作基础》之后才能选修。

我们称《Windows操作基础》是《Windows程序设计》的先修课。

每门课的直接先修课最多只有一门。

两门课可能存在相同的先修课。

你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修条件。

假定课程之间不存在时间上的冲突。

输入格式
输入文件的第一行包括两个整数N、M（中间用一个空格隔开）其中1≤N≤300,1≤M≤N。

接下来N行每行代表一门课，课号依次为1，2，…，N。

每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。

学分是不超过10的正整数。

输出格式
输出一个整数，表示学分总数。

输入样例：
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
输出样例：
13

思路： 按照树的层次划分阶段，第一维状态为节点，第二维为背包体积。那么由子节点转移过来，按照背包的放与不放来转移。实际上还是在跑分组背包，只不过u的子状态是子节点v，而不是u-1。

ACNEW：
实践证明，进行范围限制再进行刷表是最快的方法。对于这种依赖问题有dfs序的高效解法。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>using namespace std;typedef long long ll;const int maxn = 1007;int a[maxn];
int head[maxn],nex[maxn],to[maxn],tot;
int f[maxn][maxn];//当前根节点为i，选了j个点的最大学分和。
int siz[maxn];
int n,m;void add(int x,int y) {to[++tot] = y;nex[tot] = head[x];head[x] = tot;
}void DP(int u) {f[u][1] = a[u];siz[u] = 1;for(int i = head[u];i;i = nex[i]) {int v = to[i];DP(v);for(int j = min(siz[u],m + 1);j >= 1;j--) { //根节点和之前子树选了多少for(int k = 0;k + j <= m + 1 && k <= siz[v];k++) { //当前子树选了多少f[u][j + k] = max(f[u][j + k],f[v][k] + f[u][j]);}}siz[u] += siz[v];}
}int main() {scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) {int x,y;scanf("%d%d",&x,&y);add(x,i);a[i] = y;}DP(0);printf("%d\n",f[0][m + 1]);return 0;
}

dfs序优化方法
定义 $f [i] [j]$ 为选dfs序大于等于 $i$ 的点，至多选 $j$ 个的最多学分。
那么转移就是，对于 $d f s$ 序为 $i$ 的点选与不选。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>using namespace std;typedef long long ll;const int maxn = 1007;int a[maxn];
int head[maxn],nex[maxn],to[maxn],tot;
int st[maxn],ed[maxn];
int f[maxn][maxn];//当前根节点为i，选了j个点的最大学分和。
int siz[maxn],mp[maxn];
int n,m,cnt;void add(int x,int y) {to[++tot] = y;nex[tot] = head[x];head[x] = tot;
}void dfs(int u) {siz[u] = 1;st[u] = ++cnt;mp[cnt] = u;for(int i = head[u];i;i = nex[i]) {int v = to[i];dfs(v);siz[u] += siz[v];}
}int main() {scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) {int x,y;scanf("%d%d",&x,&y);add(x,i);a[i] = y;}dfs(0);f[n + 2][0] = 0;for(int i = n + 1;i >= 1;i--) {int x = mp[i];for(int p = 1;p <= m + 1;p++) {f[i][p] = max(f[i + siz[x]][p],f[i + 1][p - 1] + a[x]);}}printf("%d\n",f[1][m + 1]);return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;const int maxn = 305;
vector<int>G[maxn];
int dp[maxn][maxn];//以u为根节点，选了m个课的最优结果。
int a[maxn];
int n,m;void dfs(int u)
{dp[u][0] = 0;for(int i = 0;i < G[u].size();i++){int v = G[u][i];dfs(v);for(int j = m;j >= 0;j--)//背包{for(int k = j;k >= 0;k--)//分组{dp[u][j] = max(dp[u][j],dp[v][k] + dp[u][j - k]);}}}if(u != 0){for(int t = m;t > 0;t--)dp[u][t] = dp[u][t - 1] + a[u];//当前这个物品要选}
}int main()
{scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++){int x;scanf("%d%d",&x,&a[i]);G[x].push_back(i);}memset(dp,0xcf,sizeof(dp));dfs(0);printf("%d\n",dp[0][m]);return 0;
}