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

ydc的博客

 
 
 

日志

 
 

CF 221 div1 E  

2013-12-28 23:23:59|  分类: codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
由于当年研究vani的单纯形模板研究一天没看懂
所以有些畏惧……
于是跑去看delayyy的题解,写了那个O(n^3)的dp

一个挺好的dp题
delayyy的题解是很详细了……配上delayyy代码就真的很好懂了
转模型就是在一棵树上选nBlack个点,每个点能覆盖距离他不超过x的所有点,然后选每个点的代价是0/1。问最小花费
dp[i][j][k]表示子树i,选了j个点……然后最关键的是,再来一个点k来辅助覆盖!
辅助覆盖,顾名思义,k这个点最起码要覆盖i……也就是,选k这个点,i的内部再选一些点,覆盖i这个子树
与之对应的,我们定义ans[i][j]表示选j个点覆盖子树i的最小代价
dp[i][j][k]的这个k是不算入j里面去的……所以才叫辅助覆盖
dp[i][j][k]由子树信息合并得到,然后用来推ans[i][j]
具体转移可以看代码

学到了一个很好的均摊分析时间复杂度的模型
大家可以尝试着证明一下为何是O(n^3)的
提示1:每个点的用时是他在DFS序中位置(by delayyy)
提示2:其实这就相当于是在枚举树上所有点对

其实很久以前就有一种树形背包的题……比如选课
徐持衡在09年的集训队论文里提出了O(nV)时间复杂度的求解树形背包算法,V是容量
而选课这种题,容量与物品同阶,物品体积均为1
所以使用这个做法的话……
不需要徐持衡的优化版树形背包!
直接暴力做就是O(n^2)->O(nV)的!!

还听说了个事情
当年叉姐出“noip普及组模拟题”
给1000个带权点的树,求大小为k的联通块的最小权值。

正解是点分治+树形dp
考场上有人暴力树形dp在循环上加上界的优化
过掉了
叉姐一直以为是自己数据出水了
事实上……暴力树形dp就是O(n^2)的啦啦啦
  评论这张
 
阅读(403)| 评论(4)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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