JHwong

用户名：dotcpp0724243

访问量：834

签　名：

等　　级
排　　名	3391
经　　验	1946
参赛次数	11
文章发表	16
年　　龄	0
在职情况	学生
学　　校	宁波大学科学技术学院
专　　业

　　自我简介：

TA的其他文章

蓝桥第7/8届练习题解
浏览：89

你可能喜欢

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

C语言程序设计教程（第三版）课后习题12.2 （C语言代码）

1318: 选课（解析：C++实现）

　　作者: JHwong　　　　发表时间：2024-01-13 13:51:19 浏览：39　|　评论：0　

原题链接：选课

# 选课
## 思路解析
这道题是很明显的有依赖背包问题，或者说是树形DP。但是，事实上这道题作完了，我还是感觉是处理了森林这样的数据结构。一开始，读完题目就反应到不是正常的树形DP，而是森林DP的样子。所以想着需要预处理森林。森林有两种处理方式：超级源点/孩子兄弟表示法。看到题目输入有提到建立了超级远点0。于是就想着不用处理森林，因为题目已经协助处理。但是到后面优化的时候，还是觉得孩子兄弟表示法更合理。
首先，可以快速定义出dp[root]\[number\] = 以root为根选取number个节点的最大值。但是，很快就能反映到会出现问题。因为这样虽然最后答案是dp[0]\[m + 1\]。但是，dp[0]\[m + 1\]确实从dp[root1]\[k1\] + dp[root2]\[k2\] + ... + dp[rootn]\[kn\]构成，也就是会产生一个排列组合的问题。所以为了避免这样的情况发生，很容易就想到提前和兄弟划分选取的节点问题 -- 分治思想。其实也是加法结合律和划分具有独立划分的特殊性。
综上，我们发现需要记录整个过程的孩子、兄弟关系。所以最终处理的方式是超级源点+孩子兄弟表示法。答案是dp[0]\[m + 1\]。修改一下模板即可。
## 代码实现
```cpp
/* 
 * 题目 1318: 选课
 * 一道有依赖DP，或者说是树形dp（可能是森林，考虑预处理）。不用了题目建设了超级原点0
 * dp[root][number] = 以root为根选取number个节点的最大值， answer = dp[0][m + 1];
 * 但是，最后还要处理dp[root1][...] + dp[root2][...] + ...的问题，这显然不合理。
 * dp[root][number] = 以root为根及其之前兄弟共选number个节点的最大值。这样就处理了最后的划分问题，加速了运行。
 * 因此，需要记录孩子、兄弟关系。以及点值。因此可以是孩子兄弟表示法 -- 还是处理了森林。
 */
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAX_N 305
#define THE_NULL -1
#define INT_MIN 0x80000000

int dp[MAX_N][MAX_N], bro[MAX_N], son[MAX_N], val[MAX_N];
void add(int f, int s) {
  bro[s] = son[f];
  son[f] = s;
  return;
}
int dfs(int u, int number) {
  if (number == 0 || u == THE_NULL) return 0;
  if (dp[u][number] != THE_NULL) return dp[u][number];
  int m = dfs(bro[u], number); // 兄弟之间没有约束关系，只是简化流程 -- 因此需要考虑全给
  for (int k = 0; k < number; ++k) {
	m = std::max(m, dfs(son[u], k) + dfs(bro[u], number - k - 1) + val[u]);
  }
  return dp[u][number] = m;
}
int n, m;
int main() {
  memset(son, THE_NULL, sizeof(son));
  memset(bro, THE_NULL, sizeof(bro));
  memset(dp, THE_NULL, sizeof(dp));
  scanf("%d %d", &n, &m);
  { 
	int f, v;
	for (int i = 1; i <= n; ++i) {
	  scanf("%d %d", &f, &v);
	  val[i] = v;
	  add(f, i);
	}
  }
  printf("%d\n", dfs(0, m + 1));
  return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JHwong

TA的其他文章

你可能喜欢

字符串输入输出函数（Java代码）

点我有惊喜！你懂得！

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题12.2 （C语言代码）

1318: 选课（解析：C++实现）

评论区

精彩推荐

简单的a+b （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3)，复杂度最低的方法没有之一！！！！！

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

妹子杀手的故事（C语言代码）

简单的a+b （C语言代码）

九宫重排（C++代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

打印十字图（C语言代码）

1013题解

1048题解（读入回车问题）

JHwong

TA的其他文章

你可能喜欢

字符串输入输出函数 （Java代码）

点我有惊喜！你懂得！

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码） 如果a<0，那就不是这个代码了，哈哈哈哈

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题12.2 （C语言代码）

1318: 选课（解析：C++实现）

评论区

精彩推荐

简单的a+b （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3)，复杂度最低的方法没有之一！！！！！

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

妹子杀手的故事 （C语言代码）

简单的a+b （C语言代码）

九宫重排 （C++代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

打印十字图 （C语言代码）

1013题解

1048题解（读入回车问题）

字符串输入输出函数（Java代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

母牛的故事（C语言代码）

　　评论区

妹子杀手的故事（C语言代码）

九宫重排（C++代码）

打印十字图（C语言代码）