这是一个创建于 2978 天前的主题，其中的信息可能已经有所发展或是发生改变。
有一颗 n 节点的最多三叉的树，最多有 1000 个节点。 现在我要取其中的 m 个节点， m 不超过 100 想要的是取得所有点和与所有点相邻的点的和要最大 有点没有思路啊，求解。
第 1 条附言 · 2016-09-28 23:36:21 +08:00
看了一下确实排版的不是特别好，这个题因为涉及到容斥所以 dp 还得带记忆，非常苦恼
 |
1
WinterWu 2016-09-28 22:07:48 +08:00
1. 先把问题理顺了
2. 再把问题排版好 |
 |
2
iEverX 2016-09-28 23:26:58 +08:00
wap 的算法题啊
|
|
3
iEverX 2016-09-28 23:27:38 +08:00
如果是，那么不是树，是图吧
|
 |
4
masterjason OP @iEverX 就是树啊其实，说是说图
|
|
5
masterjason OP @WinterWu 我排版的时候打了回车的啊，不晓得怎么没了
|
|
6
iEverX 2016-09-28 23:32:25 +08:00
@masterjason 嗯， 又看了一遍，确实是树。。
|
|
7
masterjason OP @iEverX 有啥思路么。。。这个树状 dp 的话转移方程也太难写了
|
|
8
iEverX 2016-09-28 23:37:34 +08:00
@masterjason 没有，不过这是一个二叉树
|
|
9
masterjason OP @iEverX 为啥是二叉啊，最多三个门呢，你直接算有一个连到父节点了吗
|
|
10
iEverX 2016-09-28 23:49:05 +08:00
@masterjason 是啊，三叉的话就是 4 个门了
|
 |
11
zhy0216 2016-09-29 05:49:14 +08:00
这 m 个节点要连接在一起的么?
|
|
12
masterjason OP @zhy0216 不用啊，就是你选了一个点和他相临的点也默认选中
|
|
13
masterjason OP @iEverX 早上起来又想了下还是没有思路，应该是用动规的吧
|
|
14
iEverX 2016-09-29 13:11:20 +08:00
@masterjason 用动态规划写了，开了个三维数组。记忆的话，只需要保留两层就行了
|
|
15
masterjason OP @iEverX ac 了么，第一题的那些小方块会重复的么
|
|
16
iEverX 2016-09-30 13:56:38 +08:00
@masterjason 没试。。第一题不是说只有这么多的小方块，每个用一次
|
Select Language