讨论 - 管理员进。我认为这题题解、标程、数据有误

guoshi3 2008-11-22 06:56:00

点我顶贴收藏删除

呵呵，其实是废话，标程是按照题解写的，数据是根据标程生成的。题解错了当然全错。

下面我说说我对题解的看法，大家一起来看看。

光从状态设计来说，我认为不够。“设DP[I,0]表示第I个节点不放人时看守住以I为根的树所需要的人数的最小值，DP[I,1]表示第I个节点放人时看守住以I为根的树所需要的人数的最小值。”

状态转移：“

DP[I,1]=求和(min(DP[k,0],DP[k,1]))(k为孩子节点)

DP[I,0]=求和(min(DP[k,0],DP[k,1]))+DP[u,1]”

DP[I,0]的转移没有问题。但是DP[I,1]的转移有问题。它取得是每个孩子（设为J）放人或不放人看守住J这颗子树的最小人数。但是，不难想到，如果J节点不放人，且J节点本身未被看守住。这种状态也能转移到DP[I,1]的。（因为DP[I,1]中I节点上是放人的,能看守住J。）所以这时状态转移是不全面的。归根结底是状态设计的不全面。

我觉得应该设计三个状态。a[i]表示该节点放人。b[i]表示该节点不放人，但是已经被罩。c[i]表示该节点不放人，并且未被罩。状态转移方程和之前类似。复杂度不变。

#1 guoshi3@2008-11-09 19:21:00

回复删除

所以我们得60分的应该是ac~~呵呵

我说的60分是1 2 8 9四个点不过。不是有些人1 2 3 4不过....- -！

#2 xiaokeke@2008-11-09 19:24:00

回复删除

我同意GUOSHI3的想法

我也这么想的

#3 phoeagon@2008-11-09 19:30:00

回复删除

确实如此～我得小胖ac了，这个反而～

#4 lychees@2008-11-09 20:29:00

回复删除

我的也是 ...#

#5 lychees@2008-11-09 20:39:00

回复删除

我做小胖的时候也之考虑了两种状态...

再此之前我也是刚刚接触树型DP...

第一次见当要分三种情况讨论的类型...

分别是

这个点有人

下面有人

上面有人

三种情况...

在这里可以举出一个反例..

考虑四个节点连接成一条线..

中间两个没有人,外面两个有人..

这种情况只考虑两种状态的话是不会被考察到的...

#6 guoshi3@2008-11-11 17:45:00

回复删除

renqing在哪里？~~~小bin呢

#7 wish@2008-11-21 03:19:00

回复删除

顶起~

希望管理员能看见

搞的我两次 UNAC，不爽。。。

#8 xijisoft@2008-11-22 06:56:00

回复删除

我是出题人，这题数据给的有点问题，你们的方法是对的。数据早已给了RenQing，只是他这段忙NOIP，一直没有上传啊。