Ai 2008-11-09 18:35:00
点我顶贴
收藏
删除
12
0 1 1
1 1 2
2 1 3
3 1 4
4 1 5
5 1 6
6 1 7
7 1 8
8 1 9
9 1 10
10 1 11
11 0
对于这个数据其实就是下面这一条链
0-1-2-3-4-5-6-7-8-9-10-11
那么显然
1监视0 1 2
4监视3 4 5
7监视6 7 8
10监视9 10 11
我的树形Dp程序得出4个
而OIBH上发布的标程答案却是6
大家帮忙看看
#2 lizhixin@2008-11-09 05:52:00
8703
回复
删除
我的也是
请问
21
0 5 1 2 3 4 5
4 1 7
5 1 6
7 1 9
6 1 8
9 1 10
10 1 11
11 1 12
12 1 13
13 1 14
14 1 15
15 1 16
16 1 17
17 1 18
18 1 19
19 1 20
标程得9,我觉得应该得7,您看对吗
#3 Ai@2008-11-09 06:04:00
8704
回复
删除
我的树形Dp是这样表示的
f[i,1],表示在i有人监视的最小值
f[i,2],表示在i没有人监视,但i能被她的孩子监视的最小值
f[i,3]表示在i没有人监视,且i不能被她的孩子监视到的最小值,这时需要他的父亲去监视她.
f[i,1]=sigma(min(f[k,1],f[k,2],f[k,3]))+1；
f[i,3]=sigma(f[k,2])
更新f[i,2]的时候特别注意以下
f[i,2]=sigma(min(f[k,1],f[k,2]))；
如果在这一步中所有的f[k,1]都小于f[k,2],则再枚举一个f[k,1]去替换f[k,2],再取最小值
我觉得我应该没错阿
结果就wa了
#5 Ai@2008-11-09 06:09:00
8706
回复
删除
等以下 我刚刚说错了
应该是
如果在这一步中所有的f[k,1]都大于f[k,2],则再枚举一个f[k,1]去替换f[k,2],再取最小值