有一颗 n 节点的最多三叉的树，最多有 1000 个节点。 现在我要取其中的 m 个节点， m 不超过 100 想要的是取得所有点和与所有点相邻的点的和要最大 有点没有思路啊，求解。
This topic created in 3687 days ago, the information mentioned may be changed or developed.
Supplement 1 · Sep 28, 2016
看了一下确实排版的不是特别好，这个题因为涉及到容斥所以 dp 还得带记忆，非常苦恼
 |
WinterWuSep 28, 2016
1
1. 先把问题理顺了
2. 再把问题排版好 |
 |
iEverXSep 28, 2016
2
wap 的算法题啊
|
|
iEverXSep 28, 2016
3
如果是，那么不是树，是图吧
|
 |
4
@iEverX 就是树啊其实，说是说图
|
|
5
@WinterWu 我排版的时候打了回车的啊，不晓得怎么没了
|
|
iEverXSep 28, 2016
6
@masterjason 嗯， 又看了一遍，确实是树。。
|
|
7
@iEverX 有啥思路么。。。这个树状 dp 的话转移方程也太难写了
|
|
iEverXSep 28, 2016
8
@masterjason 没有，不过这是一个二叉树
|
|
9
@iEverX 为啥是二叉啊，最多三个门呢，你直接算有一个连到父节点了吗
|
|
iEverXSep 28, 2016
10
@masterjason 是啊，三叉的话就是 4 个门了
|
 |
zhy0216Sep 29, 2016
11
这 m 个节点要连接在一起的么?
|
|
12
@zhy0216 不用啊，就是你选了一个点和他相临的点也默认选中
|
|
13
@iEverX 早上起来又想了下还是没有思路，应该是用动规的吧
|
|
iEverXSep 29, 2016
14
@masterjason 用动态规划写了，开了个三维数组。记忆的话，只需要保留两层就行了
|
|
15
@iEverX ac 了么，第一题的那些小方块会重复的么
|
|
iEverXSep 30, 2016
16
@masterjason 没试。。第一题不是说只有这么多的小方块，每个用一次
|
Select Language