f [ i ] [ 0 ] += max ( f [ i ] [ 0 ] , f [ i ] [ 1 ] )
不访问当前节点 ,也可以不访问相邻的节点 否则 30 分 |
|
我感觉像记忆化搜索?????
|
|
题目 593 [USACO Nov10] 拜访奶牛
2014-09-19 18:22:48
|
|
我想着直接最大独立集不就行了么QAQ
蒟蒻最不喜欢dp了
题目 593 [USACO Nov10] 拜访奶牛
2014-09-19 17:09:29
|
|
不要忘记最后Max(f[1],g[1])因为忘了写这个,错了4组数据
|
|
树形DP,填根节点时先填其儿子节点,全题设一号节点为根节点。
f[i][1]表示拜访奶牛i所得到的最大拜访量。 f[i][0]表示不拜访奶牛i所得到的最大拜访量。 用了递归。 目标状态为:f[1][0]与f[1][1]中大的一个。 |