【围栏问题】

题目描述

在一片草原上,有 n 只兔子无忧无虑地生活着。这片草原可以划分成 m×m 的方阵。每个方格内最多有一只兔子。
一位饲养员负责喂养这些兔子。为了方便,她需要用篱笆建造最多 k 座围栏,将草原上的兔子全部围起来。
围栏需要满足以下条件:
(1)必须沿着网格线建造;
(2)每座围栏是一个不与自身重叠或相交的封闭回路;
(3)各座围栏之间互相不重叠、不相交;
(4)一座围栏不能被围在另一座围栏里面。
请你帮助饲养员计算一下围栏总长度的最小值。

输入格式

输入第 1 行为三个整数 m,k,n。
接下来 n 行每行为一对正整数 x,y,表示第 x 行第 y 列的方格中有一只兔子。

输出格式

输出仅 1 行,为一个正整数,表示围栏总长度的最小值。

样例数据 1

输入

6 1 4
1 3
4 2
4 4
6 4

输出

18

样例数据 2

输入

6 2 4
1 3
4 2
4 4
6 4

输出

16

备注

【样例1解释】
如图3-1是一种满足题意的建造方法。

【样例2解释】
如图3-2是一种满足题意的建造方法。

【数据范围】
对于 10% 的数据,k=1;
对于 10%~30% 的数据,k=2;
对于 30%~60% 的数据,n≤10;
对于 100% 的数据,1≤k≤n≤16,m≤1,000。

首先,两个围栏互相包含的情况不可能在最优解中出现(把里面那个拆掉可以节省篱笆,得到一个更优解)。

其次,两个围栏相交的情况也一定不是最优,如下图所示,把重叠的部分拆掉可以得到更优解。
由于我们的目标是最小化周长,可以得到这样一条重要性质:矩形的围栏比不规则形状的更优。如图:

把里面的边往外平移,成为一个矩形的边框,这样可以在周长不变的情况下,围住更多的土地。(不用担心扩展出去的部分会和另外的围栏相交,因为这不可能在最优解中出现,刚才已经提到)

有些情况下,矩形边框不仅扩大围住的范围而且能节省周长。

所以,接下来我们只需考虑用矩形去包围兔子就够了。

定义基本矩形或叫极小矩形——假如这个矩形再往里缩小一点就会有兔子从里面逃出。

如上图就不是一个极小矩形,它可以往里收缩。

现在它是一个极小矩形。
容易发现,最优解中必然只包含极小矩形。
我们可以预处理出所有极小矩形:枚举所有兔子的非空子集,找出这个子集中最上、最左、最右、最下的兔子,就可得到一个极小矩形。(当然这样计算会出现许多重复的,剔除即可)。这种做法虽然是指数级的但是编码简单,而且n很小,仍可接受。
现在我们有了一堆矩形,对于每个矩形我们掌握它的两个属性:周长、围住了的兔子集合。问题转化为:从这堆矩形中选出不超过k个,在满足这些兔子集合互不相交,且其并集恰好是兔子全集的条件下,最小化总周长。
这是一个典型的精确覆盖问题,搜索解决即可。可以使用二进制来表示各个集合,用位运算的方法达到优化的效果。也可以用DLX来做,更快。

Dancing Link(舞蹈链)中文版:http://io.sqybi.com/dlxcn/

PDF下载:http://pan.baidu.com/s/1pJMHEdl

那么问题来了,我并不会DLX!!!!这周之内摸索出DLX然后争取把题解发上来!

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*