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

大家帮忙看看

请问

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,您看对吗

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了

应该是

如果在这一步中所有的f[k,1]都大于f[k,2],则再枚举一个f[k,1]去替换f[k,2],再取最小值