USACO/fence8

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 6 .3中的OI题目Fence Rails的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。

问题分析

抽象一下就可以发现，算法的本质是多重背包问题。

补充：这题与破锣乐队都是多个背包，不可重复放物品。区别在于破锣乐队要有顺序，此题不需要，这样此题就必须要搜索才行。

单个背包的问题我们可以用DP解决，但是对于这种问题我们只能用搜索了。

但是可以看一看这道题的数据规模：1<=n<=50，1<=r<=1023。如此大的规模我们只能考虑进一步的优化。

我采用的是dfsid搜索每一个rail来源的board。以下技巧都是针对这种搜索顺序来制定的。

(注：rail是所需要切成的东西，board是供应商提供的原料）

如果使用dancing links的话，可以让程序的常数快2倍。

优化技巧

1. 很容易就能注意到，由于每块rail的价值是相等的——也就是说切小的要比切大的来的划算。那么我们在搜索能否切出i个rail的方案是自然要选最小的i个rail来切。
2. 经过一些实验可以发现，先切大的rail比先切小的rail更容易提前出解。

   #[先切小的board比先切大的board更容易提前出解？]
   #{注：好像先切大的board要比先切小的更快}。
   #{*我的程序先切小再切大第5个点就TLE了,而先切大再切小就快很多,见C++程序.}
   #{跟我一样，握个手，一定要先大后小！！！}

1. 由于r最大可能是1023，但是rail长度的范围却只有0~128，这点提醒了我们有很多rail的长度会是相同的。所以我们要避免冗余，优化搜索顺序。若有rail[i+1]=rail[i]，则rail[i+1]对应的board一定大于等于rail[i]对应的board。可以通过这种方法剪掉很多冗余的枝条。
2. 相应的，如果board[i]=board[i+1]，那么从board[i]切下的最大的rail一定大于等于从board[i+1]切下的最大的rail。
3. 二分答案
4. 对于切剩下的board（无法再切下rail），统计一下总和。如果这个值大于board长度的总和减去rail长度的总和，一定无解，可以剪枝。这个剪枝最关键。(这个要基于二分答案)
5. 其实在读入的过程中，如果rail[i] > max{board} 那么这个rail应该舍去 By Clarkok

加上上述优化策略后，程序就能很快出解了。

另外的优化

我的是搜哪几个b相加能得到a

剪枝：

1.当前深度下b的总值大于a的总值，CUT！

2.从大到小搜b

3.对于当前搜到的b，如果向前推几位，相加后恰能得到当前搜到的a，那么这几个b都加到此a里（证明我在纸上写了好几页。。）

4.深度30，30地增加，然后再在这30区间内搜一遍

OVER。。

---

哪位可以解释一下 对于切剩下的board（无法再切下rail），统计一下总和。如果这个值大于board长度的总和减去rail长度的总和，一定无解，可以剪枝。 俺很不懂诶。。

[我猜想：这里“rail长度的总和”指的是二分之后的，即“必须被切出的rail”。所以“board长度的总和减去rail长度的总和”=最多可以浪费的。]

参考代码

C

C++

Pascal