注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

keky的博客

GAIN CONFIDENCE _=_!既然选择了远方,便只顾风雨兼程^_^

 
 
 

日志

 
 

hoj-2500_你差点累死我!  

2007-09-20 15:46:03|  分类: cs_acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

        这两天做题的劲很足,于是昨天就上Oj 打算好好干一番, expect up to 180;但做到178时,时间已剩不多了就随便上STATUS找个题做做,一不小心就碰上2500,xiaoB,可把握给气坏了,初看题好像很面熟,好像以前做过类是的题,用简单的将树分层就可以得出结果, 后面老是WA, 实在不行了找xiaoE取经去了,当时他就说DP,也没太注意问到底怎么回事,今天下午没课就有跟它干起来了,因为没 A 的感觉真不爽啊!上DISCUSS看了别人发的帖子,才知道要用TREE_dp,好像很深奥、没用过,看看了状态转移方程也就开始改CODE了。

        功夫不负用心人,经过几个小时的思考和修改终于过了,现在就来说说怎么做吧。

        状态转移方程:dp[ father[i][0] ] = max{ dp[i][0], dp[i][1] } ; 其中dp[i][0] 以i为结点是自己不选的总数,dp[i][1]为自己也选上的总数。初始化 dp[][0] = 0; dp[][1] = 1; 我是首先将树分层,然后从树的最底层开始 dp,这样就解决了求最大值的问题了。

           接着就是判断该种选法是不是唯一,用一个数组,ch[][]  ={ 0 } 来标记,"1"表示该选法不唯一, "0" 唯一;

ch[ fth[i]][1] = ch[i][0]; 

ch[ fth[i][0]] = 1( if( dp[i][0] == dp[i][1] || dp[i][x] = 1 ( dp[i][x]= max( dp[i][0], dp[i][1] ) )))

 因为dp[i][0]有两种选择故用X表示之,而且当i的两种选法都相等那就说明dp[fth[i]][0]就有两种选法(不唯一),因此结果只要选老大结点的较大值输出就行,当其ch[0][x] == 1|| dp[0][0] == dp[0][1] 则说明情况不唯一,否则就yes!

           嘿嘿,搞定了!该好好歇息了。   努力再努力!

        

  评论这张
 
阅读(38)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017