dancing link

2015年4月1日1,5682

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

我们只要知道一件事情

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

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

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

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

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

贴一波代码 hust1017 fzu1686 hdu2295

hust1017 精确覆盖

应该没有更裸的了

fzu1686 裸重复覆盖

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

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

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

hdu2295

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

 

  • 吴钰晗2015年4月1日 下午4:33 回复

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

    #1  
    • hzwer2015年4月1日 下午6:17 回复
      admin

      不是吧。。可能是我服务器太烂了

      #11