USACO/holstein

分析

对于每种饲料，只有两种选择：喂或者不喂。所以最多只能有2^15种方案，简单的枚举就可以了。

可以枚举1 to 2^p-1的长度为p的二进制来获得每个养料是否要，0表示不要，1表示要。

如m=3则枚举3位的二进制: 001 010 011 100 101 110 111 以上就对应了除了都不取外的7种情况。

下面是2^p-1的表：

const bin:array[1..15]of integer=

(1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767);

当然，2^p-1可以用1 shl p-1 代替

---

或者我们也可以dfs,决策是取或不取第now个原料,当不可能是最优解(nown>totn)时回溯;如果营养满足就记录最优解回溯;如果g个饲料都决策完了但营养仍不足则回溯.很容易写,很漂亮.

BFS

BFS结合位运算加速,并且用一个数组记录已计算过的前缀,很容易大幅度剪枝.而且一得到解就能返回,因为BFS最先找到的 定是最优解.代码见C++

参考代码

C
C++
Pascal
Java

引用

[1]

[2]