dancing link

2015年4月1日4,4002

其实感觉就是个搜索的优化

我们只要知道一件事情

就是双向链表中删除一个元素x

l[r[x]]=l[x],r[l[x]]=r[x]

这时候实际上x元素的左右指针没有被改变

所以可以很容易地恢复回来

然后看看代码应该就不难理解了

贴一波代码 hust1017 fzu1686 hdu2295

hust1017 精确覆盖

应该没有更裸的了

fzu1686 裸重复覆盖

实际上重复覆盖仅仅是在精确覆盖基础上略微改动一些

主要是加入一个估价函数,即当前状态至少还需要的步数

从左往右扫每一列,若该列没有元素被选,由于我们不知道选哪个是较优的,于是就同时选取所有元素,代价记为1,显然最后会得出代价的下界

hdu2295

二分以后就是喜闻乐见的重复覆盖

 

avatar
1 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
hzwer Recent comment authors
  Subscribe  
提醒
吴钰晗

黄学长您在发博文的时候我们是不是进不了网站?