分析
对于一个关系树,对于一个父节点来说,根据题目条件,父节点和他的直接子节点不可能出现在同一个方案里面,我们如果说选择父节点,子节点就肯定一个都不会选,如果说不选父节点,我们在这里肯定是需要做一个决策,选择子节点和不选择子节点哪一个更好。
我们用f[i][2]来表示我们的状态。
i代表当前的点,第二维中的1代表我们选择这个点,0就表示我们不选择这个点。
对于一个相对父节点
选择这个父节点
1 | f[i][1]+=f[k][0]//对于一个子节点k |
不选择这个父节点
1 | f[i][0]+=max(f[k][0],f[k][1]); |
代码
1 | #include <iostream> |
本文作者: jiangyuhao
本文链接: http://example.com/2022/04/18/%E6%B2%A1%E6%9C%89%E4%B8%8A%E5%8F%B8%E7%9A%84%E8%88%9E%E4%BC%9A/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!